1 /* 2 * DATA STRUCTURE AND MACRO DEFINITIONS for Sparse. 3 * 4 * Author: Advising professor: 5 * Kenneth S. Kundert Alberto Sangiovanni-Vincentelli 6 * UC Berkeley 7 * 8 * This file contains common type definitions and macros for the sparse 9 * matrix routines. These definitions are of no interest to the user. 10 */ 11 12 13 /* 14 * Revision and copyright information. 15 * 16 * Copyright (c) 1985,86,87,88 17 * by Kenneth S. Kundert and the University of California. 18 * 19 * Permission to use, copy, modify, and distribute this software and 20 * its documentation for any purpose and without fee is hereby granted, 21 * provided that the copyright notices appear in all copies and 22 * supporting documentation and that the authors and the University of 23 * California are properly credited. The authors and the University of 24 * California make no representations as to the suitability of this 25 * software for any purpose. It is provided `as is', without express 26 * or implied warranty. 27 * 28 * $Date: 88/06/18 11:13:40 $ 29 * $Revision: 1.2 $ 30 */ 31 32 33 34 35 /* 36 * IMPORTS 37 */ 38 39 #include <stdio.h> 40 #include <stdlib.h> 41 #include <string.h> 42 43 44 /* 45 * If running lint, change some of the compiler options to get a more 46 * complete inspection. 47 */ 48 49 #ifdef lint 50 #undef REAL 51 #undef spCOMPLEX 52 #undef EXPANDABLE 53 #undef TRANSLATE 54 #undef INITIALIZE 55 #undef DELETE 56 #undef STRIP 57 #undef MODIFIED_NODAL 58 #undef QUAD_ELEMENT 59 #undef TRANSPOSE 60 #undef SCALING 61 #undef DOCUMENTATION 62 #undef MULTIPLICATION 63 #undef DETERMINANT 64 #undef CONDITION 65 #undef PSEUDOCONDITION 66 #undef FORTRAN 67 #undef DEBUG 68 #undef spCOMPATIBILITY 69 70 #define REAL YES 71 #define spCOMPLEX YES 72 #define EXPANDABLE YES 73 #define TRANSLATE YES 74 #define INITIALIZE YES 75 #define DELETE YES 76 #define STRIP YES 77 #define MODIFIED_NODAL YES 78 #define QUAD_ELEMENT YES 79 #define TRANSPOSE YES 80 #define SCALING YES 81 #define DOCUMENTATION YES 82 #define MULTIPLICATION YES 83 #define DETERMINANT YES 84 #define CONDITION YES 85 #define PSEUDOCONDITION YES 86 #define FORTRAN YES 87 #define DEBUG YES 88 #define spCOMPATIBILITY YES 89 90 #define LINT YES 91 #else /* not lint */ 92 #define LINT NO 93 #endif /* not lint */ 94 95 96 97 98 99 100 101 /* 102 * MACRO DEFINITIONS 103 * 104 * Macros are distinguished by using solely capital letters in their 105 * identifiers. This contrasts with C defined identifiers which are strictly 106 * lower case, and program variable and procedure names which use both upper 107 * and lower case. 108 */ 109 110 /* Begin macros. */ 111 112 /* Boolean data type */ 113 #define BOOLEAN int 114 #define NO 0 115 #define YES 1 116 #define NOT ! 117 #define AND && 118 #define OR || 119 120 /* NULL pointer */ 121 #ifndef NULL 122 #define NULL 0 123 #endif 124 125 #define SPARSE_ID 0x772773 /* Arbitrary (is Sparse on phone). */ 126 #define IS_SPARSE(matrix) ((matrix) != NULL && \ 127 (matrix)->ID == SPARSE_ID) 128 #define IS_VALID(matrix) ((matrix) != NULL && \ 129 (matrix)->ID == SPARSE_ID && \ 130 (matrix)->Error >= spOKAY && \ 131 (matrix)->Error < spFATAL) 132 #define IS_FACTORED(matrix) ((matrix)->Factored && !(matrix)->NeedsOrdering) 133 134 /* Macro commands */ 135 /* Macro functions that return the maximum or minimum independent of type. */ 136 #define MAX(a,b) ((a) > (b) ? (a) : (b)) 137 #define MIN(a,b) ((a) < (b) ? (a) : (b)) 138 139 /* Macro function that returns the absolute value of a floating point number. */ 140 #define ABS(a) ((a) < 0.0 ? -(a) : (a)) 141 142 /* Macro function that returns the square of a number. */ 143 #define SQR(a) ((a)*(a)) 144 145 /* Macro procedure that swaps two entities. */ 146 #define SWAP(type, a, b) {type swapx; swapx = a; a = b; b = swapx;} 147 148 /* Macro function that returns the approx absolute value of a complex number. */ 149 #if spCOMPLEX 150 #define ELEMENT_MAG(ptr) (ABS((ptr)->Real) + ABS((ptr)->Imag)) 151 #else 152 #define ELEMENT_MAG(ptr) ((ptr)->Real < 0.0 ? -(ptr)->Real : (ptr)->Real) 153 #endif 154 155 /* Complex assignment statements. */ 156 #define CMPLX_ASSIGN(to,from) \ 157 { (to).Real = (from).Real; \ 158 (to).Imag = (from).Imag; \ 159 } 160 #define CMPLX_CONJ_ASSIGN(to,from) \ 161 { (to).Real = (from).Real; \ 162 (to).Imag = -(from).Imag; \ 163 } 164 #define CMPLX_NEGATE_ASSIGN(to,from) \ 165 { (to).Real = -(from).Real; \ 166 (to).Imag = -(from).Imag; \ 167 } 168 #define CMPLX_CONJ_NEGATE_ASSIGN(to,from) \ 169 { (to).Real = -(from).Real; \ 170 (to).Imag = (from).Imag; \ 171 } 172 #define CMPLX_CONJ(a) (a).Imag = -(a).Imag 173 #define CMPLX_NEGATE(a) \ 174 { (a).Real = -(a).Real; \ 175 (a).Imag = -(a).Imag; \ 176 } 177 178 /* Macro that returns the approx magnitude (L-1 norm) of a complex number. */ 179 #define CMPLX_1_NORM(a) (ABS((a).Real) + ABS((a).Imag)) 180 181 /* Macro that returns the approx magnitude (L-infinity norm) of a complex. */ 182 #define CMPLX_INF_NORM(a) (MAX (ABS((a).Real),ABS((a).Imag))) 183 184 /* Macro function that returns the magnitude (L-2 norm) of a complex number. */ 185 #define CMPLX_2_NORM(a) (sqrt((a).Real*(a).Real + (a).Imag*(a).Imag)) 186 187 /* Macro function that performs complex addition. */ 188 #define CMPLX_ADD(to,from_a,from_b) \ 189 { (to).Real = (from_a).Real + (from_b).Real; \ 190 (to).Imag = (from_a).Imag + (from_b).Imag; \ 191 } 192 193 /* Macro function that performs complex subtraction. */ 194 #define CMPLX_SUBT(to,from_a,from_b) \ 195 { (to).Real = (from_a).Real - (from_b).Real; \ 196 (to).Imag = (from_a).Imag - (from_b).Imag; \ 197 } 198 199 /* Macro function that is equivalent to += operator for complex numbers. */ 200 #define CMPLX_ADD_ASSIGN(to,from) \ 201 { (to).Real += (from).Real; \ 202 (to).Imag += (from).Imag; \ 203 } 204 205 /* Macro function that is equivalent to -= operator for complex numbers. */ 206 #define CMPLX_SUBT_ASSIGN(to,from) \ 207 { (to).Real -= (from).Real; \ 208 (to).Imag -= (from).Imag; \ 209 } 210 211 /* Macro function that multiplies a complex number by a scalar. */ 212 #define SCLR_MULT(to,sclr,cmplx) \ 213 { (to).Real = (sclr) * (cmplx).Real; \ 214 (to).Imag = (sclr) * (cmplx).Imag; \ 215 } 216 217 /* Macro function that multiply-assigns a complex number by a scalar. */ 218 #define SCLR_MULT_ASSIGN(to,sclr) \ 219 { (to).Real *= (sclr); \ 220 (to).Imag *= (sclr); \ 221 } 222 223 /* Macro function that multiplies two complex numbers. */ 224 #define CMPLX_MULT(to,from_a,from_b) \ 225 { (to).Real = (from_a).Real * (from_b).Real - \ 226 (from_a).Imag * (from_b).Imag; \ 227 (to).Imag = (from_a).Real * (from_b).Imag + \ 228 (from_a).Imag * (from_b).Real; \ 229 } 230 231 /* Macro function that implements to *= from for complex numbers. */ 232 #define CMPLX_MULT_ASSIGN(to,from) \ 233 { RealNumber to_real_ = (to).Real; \ 234 (to).Real = to_real_ * (from).Real - \ 235 (to).Imag * (from).Imag; \ 236 (to).Imag = to_real_ * (from).Imag + \ 237 (to).Imag * (from).Real; \ 238 } 239 240 /* Macro function that multiplies two complex numbers, the first of which is 241 * conjugated. */ 242 #define CMPLX_CONJ_MULT(to,from_a,from_b) \ 243 { (to).Real = (from_a).Real * (from_b).Real + \ 244 (from_a).Imag * (from_b).Imag; \ 245 (to).Imag = (from_a).Real * (from_b).Imag - \ 246 (from_a).Imag * (from_b).Real; \ 247 } 248 249 /* Macro function that multiplies two complex numbers and then adds them 250 * to another. to = add + mult_a * mult_b */ 251 #define CMPLX_MULT_ADD(to,mult_a,mult_b,add) \ 252 { (to).Real = (mult_a).Real * (mult_b).Real - \ 253 (mult_a).Imag * (mult_b).Imag + (add).Real; \ 254 (to).Imag = (mult_a).Real * (mult_b).Imag + \ 255 (mult_a).Imag * (mult_b).Real + (add).Imag; \ 256 } 257 258 /* Macro function that subtracts the product of two complex numbers from 259 * another. to = subt - mult_a * mult_b */ 260 #define CMPLX_MULT_SUBT(to,mult_a,mult_b,subt) \ 261 { (to).Real = (subt).Real - (mult_a).Real * (mult_b).Real + \ 262 (mult_a).Imag * (mult_b).Imag; \ 263 (to).Imag = (subt).Imag - (mult_a).Real * (mult_b).Imag - \ 264 (mult_a).Imag * (mult_b).Real; \ 265 } 266 267 /* Macro function that multiplies two complex numbers and then adds them 268 * to another. to = add + mult_a* * mult_b where mult_a* represents mult_a 269 * conjugate. */ 270 #define CMPLX_CONJ_MULT_ADD(to,mult_a,mult_b,add) \ 271 { (to).Real = (mult_a).Real * (mult_b).Real + \ 272 (mult_a).Imag * (mult_b).Imag + (add).Real; \ 273 (to).Imag = (mult_a).Real * (mult_b).Imag - \ 274 (mult_a).Imag * (mult_b).Real + (add).Imag; \ 275 } 276 277 /* Macro function that multiplies two complex numbers and then adds them 278 * to another. to += mult_a * mult_b */ 279 #define CMPLX_MULT_ADD_ASSIGN(to,from_a,from_b) \ 280 { (to).Real += (from_a).Real * (from_b).Real - \ 281 (from_a).Imag * (from_b).Imag; \ 282 (to).Imag += (from_a).Real * (from_b).Imag + \ 283 (from_a).Imag * (from_b).Real; \ 284 } 285 286 /* Macro function that multiplies two complex numbers and then subtracts them 287 * from another. */ 288 #define CMPLX_MULT_SUBT_ASSIGN(to,from_a,from_b) \ 289 { (to).Real -= (from_a).Real * (from_b).Real - \ 290 (from_a).Imag * (from_b).Imag; \ 291 (to).Imag -= (from_a).Real * (from_b).Imag + \ 292 (from_a).Imag * (from_b).Real; \ 293 } 294 295 /* Macro function that multiplies two complex numbers and then adds them 296 * to the destination. to += from_a* * from_b where from_a* represents from_a 297 * conjugate. */ 298 #define CMPLX_CONJ_MULT_ADD_ASSIGN(to,from_a,from_b) \ 299 { (to).Real += (from_a).Real * (from_b).Real + \ 300 (from_a).Imag * (from_b).Imag; \ 301 (to).Imag += (from_a).Real * (from_b).Imag - \ 302 (from_a).Imag * (from_b).Real; \ 303 } 304 305 /* Macro function that multiplies two complex numbers and then subtracts them 306 * from the destination. to -= from_a* * from_b where from_a* represents from_a 307 * conjugate. */ 308 #define CMPLX_CONJ_MULT_SUBT_ASSIGN(to,from_a,from_b) \ 309 { (to).Real -= (from_a).Real * (from_b).Real + \ 310 (from_a).Imag * (from_b).Imag; \ 311 (to).Imag -= (from_a).Real * (from_b).Imag - \ 312 (from_a).Imag * (from_b).Real; \ 313 } 314 315 /* 316 * Macro functions that provide complex division. 317 */ 318 319 /* Complex division: to = num / den */ 320 #define CMPLX_DIV(to,num,den) \ 321 { RealNumber r_, s_; \ 322 if (((den).Real >= (den).Imag AND (den).Real > -(den).Imag) OR \ 323 ((den).Real < (den).Imag AND (den).Real <= -(den).Imag)) \ 324 { r_ = (den).Imag / (den).Real; \ 325 s_ = (den).Real + r_*(den).Imag; \ 326 (to).Real = ((num).Real + r_*(num).Imag)/s_; \ 327 (to).Imag = ((num).Imag - r_*(num).Real)/s_; \ 328 } \ 329 else \ 330 { r_ = (den).Real / (den).Imag; \ 331 s_ = (den).Imag + r_*(den).Real; \ 332 (to).Real = (r_*(num).Real + (num).Imag)/s_; \ 333 (to).Imag = (r_*(num).Imag - (num).Real)/s_; \ 334 } \ 335 } 336 337 /* Complex division and assignment: num /= den */ 338 #define CMPLX_DIV_ASSIGN(num,den) \ 339 { RealNumber r_, s_, t_; \ 340 if (((den).Real >= (den).Imag AND (den).Real > -(den).Imag) OR \ 341 ((den).Real < (den).Imag AND (den).Real <= -(den).Imag)) \ 342 { r_ = (den).Imag / (den).Real; \ 343 s_ = (den).Real + r_*(den).Imag; \ 344 t_ = ((num).Real + r_*(num).Imag)/s_; \ 345 (num).Imag = ((num).Imag - r_*(num).Real)/s_; \ 346 (num).Real = t_; \ 347 } \ 348 else \ 349 { r_ = (den).Real / (den).Imag; \ 350 s_ = (den).Imag + r_*(den).Real; \ 351 t_ = (r_*(num).Real + (num).Imag)/s_; \ 352 (num).Imag = (r_*(num).Imag - (num).Real)/s_; \ 353 (num).Real = t_; \ 354 } \ 355 } 356 357 /* Complex reciprocation: to = 1.0 / den */ 358 #define CMPLX_RECIPROCAL(to,den) \ 359 { RealNumber r_; \ 360 if (((den).Real >= (den).Imag AND (den).Real > -(den).Imag) OR \ 361 ((den).Real < (den).Imag AND (den).Real <= -(den).Imag)) \ 362 { r_ = (den).Imag / (den).Real; \ 363 (to).Imag = -r_*((to).Real = 1.0/((den).Real + r_*(den).Imag)); \ 364 } \ 365 else \ 366 { r_ = (den).Real / (den).Imag; \ 367 (to).Real = -r_*((to).Imag = -1.0/((den).Imag + r_*(den).Real));\ 368 } \ 369 } 370 371 372 373 374 375 376 /* 377 * ASSERT and ABORT 378 * 379 * Macro used to assert that if the code is working correctly, then 380 * a condition must be true. If not, then execution is terminated 381 * and an error message is issued stating that there is an internal 382 * error and giving the file and line number. These assertions are 383 * not evaluated unless the DEBUG flag is true. 384 */ 385 386 #if DEBUG 387 #define ASSERT(condition) if (NOT(condition)) ABORT() 388 #else 389 #define ASSERT(condition) 390 #endif 391 392 #if DEBUG 393 #define ABORT() \ 394 { (void)fflush(stdout); \ 395 (void)fprintf(stderr, "sparse: panic in file `%s' at line %d.\n", \ 396 __FILE__, __LINE__); \ 397 (void)fflush(stderr); \ 398 abort(); \ 399 } 400 #else 401 #define ABORT() 402 #endif 403 404 405 406 407 408 /* 409 * IMAGINARY VECTORS 410 * 411 * The imaginary vectors iRHS and iSolution are only needed when the 412 * options spCOMPLEX and spSEPARATED_COMPLEX_VECTORS are set. The following 413 * macro makes it easy to include or exclude these vectors as needed. 414 */ 415 416 #if spCOMPLEX AND spSEPARATED_COMPLEX_VECTORS 417 #define IMAG_VECTORS , iRHS, iSolution 418 #define IMAG_RHS , iRHS 419 #else 420 #define IMAG_VECTORS 421 #define IMAG_RHS 422 #endif 423 424 425 426 427 428 429 /* 430 * MEMORY ALLOCATION 431 */ 432 433 /* 434 extern void *malloc(), *calloc(), *realloc(); 435 #ifdef ultrix 436 extern void free(); 437 extern void abort(); 438 #else 439 extern free(); 440 extern abort(); 441 #endif 442 */ 443 444 #define ALLOC(type,number) ((type *)malloc((unsigned)(sizeof(type)*(number)))) 445 #define REALLOC(ptr,type,number) \ 446 ptr = (type *)realloc((char *)ptr,(unsigned)(sizeof(type)*(number))) 447 #define FREE(ptr) { if ((ptr) != NULL) free((char *)(ptr)); (ptr) = NULL; } 448 449 450 /* Calloc that properly handles allocating a cleared vector. */ 451 #define CALLOC(ptr,type,number) \ 452 { int i; ptr = ALLOC(type, number); \ 453 if (ptr != (type *)NULL) \ 454 for(i=(number)-1;i>=0; i--) ptr[i] = (type) 0; \ 455 } 456 457 458 459 460 461 462 463 /* 464 * REAL NUMBER 465 */ 466 467 /* Begin `RealNumber'. */ 468 469 typedef spREAL RealNumber, *RealVector; 470 471 472 473 474 475 476 477 478 /* 479 * COMPLEX NUMBER DATA STRUCTURE 480 * 481 * >>> Structure fields: 482 * Real (RealNumber) 483 * The real portion of the number. Real must be the first 484 * field in this structure. 485 * Imag (RealNumber) 486 * The imaginary portion of the number. This field must follow 487 * immediately after Real. 488 */ 489 490 /* Begin `ComplexNumber'. */ 491 492 typedef struct 493 { RealNumber Real; 494 RealNumber Imag; 495 } ComplexNumber, *ComplexVector; 496 497 498 499 500 501 502 503 504 /* 505 * MATRIX ELEMENT DATA STRUCTURE 506 * 507 * Every nonzero element in the matrix is stored in a dynamically allocated 508 * MatrixElement structure. These structures are linked together in an 509 * orthogonal linked list. Two different MatrixElement structures exist. 510 * One is used when only real matrices are expected, it is missing an entry 511 * for imaginary data. The other is used if complex matrices are expected. 512 * It contains an entry for imaginary data. 513 * 514 * >>> Structure fields: 515 * Real (RealNumber) 516 * The real portion of the value of the element. Real must be the first 517 * field in this structure. 518 * Imag (RealNumber) 519 * The imaginary portion of the value of the element. If the matrix 520 * routines are not compiled to handle complex matrices, then this 521 * field does not exist. If it exists, it must follow immediately after 522 * Real. 523 * Row (int) 524 * The row number of the element. 525 * Col (int) 526 * The column number of the element. 527 * NextInRow (struct MatrixElement *) 528 * NextInRow contains a pointer to the next element in the row to the 529 * right of this element. If this element is the last nonzero in the 530 * row then NextInRow contains NULL. 531 * NextInCol (struct MatrixElement *) 532 * NextInCol contains a pointer to the next element in the column below 533 * this element. If this element is the last nonzero in the column then 534 * NextInCol contains NULL. 535 * pInitInfo (char *) 536 * Pointer to user data used for initialization of the matrix element. 537 * Initialized to NULL. 538 * 539 * >>> Type definitions: 540 * ElementPtr 541 * A pointer to a MatrixElement. 542 * ArrayOfElementPtrs 543 * An array of ElementPtrs. Used for FirstInRow, FirstInCol and 544 * Diag pointer arrays. 545 */ 546 547 /* Begin `MatrixElement'. */ 548 549 struct MatrixElement 550 { RealNumber Real; 551 #if spCOMPLEX 552 RealNumber Imag; 553 #endif 554 int Row; 555 int Col; 556 struct MatrixElement *NextInRow; 557 struct MatrixElement *NextInCol; 558 #if INITIALIZE 559 char *pInitInfo; 560 #endif 561 }; 562 563 typedef struct MatrixElement *ElementPtr; 564 typedef ElementPtr *ArrayOfElementPtrs; 565 566 567 568 569 570 571 572 573 /* 574 * ALLOCATION DATA STRUCTURE 575 * 576 * The sparse matrix routines keep track of all memory that is allocated by 577 * the operating system so the memory can later be freed. This is done by 578 * saving the pointers to all the chunks of memory that are allocated to a 579 * particular matrix in an allocation list. That list is organized as a 580 * linked list so that it can grow without a priori bounds. 581 * 582 * >>> Structure fields: 583 * AllocatedPtr (char *) 584 * Pointer to chunk of memory that has been allocated for the matrix. 585 * NextRecord (struct AllocationRecord *) 586 * Pointer to the next allocation record. 587 */ 588 589 /* Begin `AllocationRecord'. */ 590 struct AllocationRecord 591 { char *AllocatedPtr; 592 struct AllocationRecord *NextRecord; 593 }; 594 595 typedef struct AllocationRecord *AllocationListPtr; 596 597 598 599 600 601 602 603 604 605 /* 606 * FILL-IN LIST DATA STRUCTURE 607 * 608 * The sparse matrix routines keep track of all fill-ins separately from 609 * user specified elements so they may be removed by spStripFills(). Fill-ins 610 * are allocated in bunched in what is called a fill-in lists. The data 611 * structure defined below is used to organize these fill-in lists into a 612 * linked-list. 613 * 614 * >>> Structure fields: 615 * pFillinList (ElementPtr) 616 * Pointer to a fill-in list, or a bunch of fill-ins arranged contiguously 617 * in memory. 618 * NumberOfFillinsInList (int) 619 * Seems pretty self explanatory to me. 620 * Next (struct FillinListNodeStruct *) 621 * Pointer to the next fill-in list structures. 622 */ 623 624 /* Begin `FillinListNodeStruct'. */ 625 struct FillinListNodeStruct 626 { ElementPtr pFillinList; 627 int NumberOfFillinsInList; 628 struct FillinListNodeStruct *Next; 629 }; 630 631 632 633 634 635 636 637 638 639 640 /* 641 * MATRIX FRAME DATA STRUCTURE 642 * 643 * This structure contains all the pointers that support the orthogonal 644 * linked list that contains the matrix elements. Also included in this 645 * structure are other numbers and pointers that are used globally by the 646 * sparse matrix routines and are associated with one particular matrix. 647 * 648 * >>> Type definitions: 649 * MatrixPtr 650 * A pointer to MatrixFrame. Essentially, a pointer to the matrix. 651 * 652 * >>> Structure fields: 653 * AbsThreshold (RealNumber) 654 * The absolute magnitude an element must have to be considered as a 655 * pivot candidate, except as a last resort. 656 * AllocatedExtSize (int) 657 * The allocated size of the arrays used to translate external row and 658 * column numbers to their internal values. 659 * AllocatedSize (int) 660 * The currently allocated size of the matrix; the size the matrix can 661 * grow to when EXPANDABLE is set true and AllocatedSize is the largest 662 * the matrix can get without requiring that the matrix frame be 663 * reallocated. 664 * Complex (BOOLEAN) 665 * The flag which indicates whether the matrix is complex (true) or 666 * real. 667 * CurrentSize (int) 668 * This number is used during the building of the matrix when the 669 * TRANSLATE option is set true. It indicates the number of internal 670 * rows and columns that have elements in them. 671 * Diag (ArrayOfElementPtrs) 672 * Array of pointers that points to the diagonal elements. 673 * DoCmplxDirect (BOOLEAN *) 674 * Array of flags, one for each column in matrix. If a flag is true 675 * then corresponding column in a complex matrix should be eliminated 676 * in spFactor() using direct addressing (rather than indirect 677 * addressing). 678 * DoRealDirect (BOOLEAN *) 679 * Array of flags, one for each column in matrix. If a flag is true 680 * then corresponding column in a real matrix should be eliminated 681 * in spFactor() using direct addressing (rather than indirect 682 * addressing). 683 * Elements (int) 684 * The number of original elements (total elements minus fill ins) 685 * present in matrix. 686 * Error (int) 687 * The error status of the sparse matrix package. 688 * ExtSize (int) 689 * The value of the largest external row or column number encountered. 690 * ExtToIntColMap (int []) 691 * An array that is used to convert external columns number to internal 692 * external column numbers. Present only if TRANSLATE option is set true. 693 * ExtToIntRowMap (int []) 694 * An array that is used to convert external row numbers to internal 695 * external row numbers. Present only if TRANSLATE option is set true. 696 * Factored (BOOLEAN) 697 * Indicates if matrix has been factored. This flag is set true in 698 * spFactor() and spOrderAndFactor() and set false in spCreate() 699 * and spClear(). 700 * Fillins (int) 701 * The number of fill-ins created during the factorization the matrix. 702 * FirstInCol (ArrayOfElementPtrs) 703 * Array of pointers that point to the first nonzero element of the 704 * column corresponding to the index. 705 * FirstInRow (ArrayOfElementPtrs) 706 * Array of pointers that point to the first nonzero element of the row 707 * corresponding to the index. 708 * ID (unsigned long int) 709 * A constant that provides the sparse data structure with a signature. 710 * When DEBUG is true, all externally available sparse routines check 711 * this signature to assure they are operating on a valid matrix. 712 * Intermediate (RealVector) 713 * Temporary storage used in the spSolve routines. Intermediate is an 714 * array used during forward and backward substitution. It is 715 * commonly called y when the forward and backward substitution process is 716 * denoted Ax = b => Ly = b and Ux = y. 717 * InternalVectorsAllocated (BOOLEAN) 718 * A flag that indicates whether the markowitz vectors and the 719 * Intermediate vector have been created. 720 * These vectors are created in CreateInternalVectors(). 721 * IntToExtColMap (int []) 722 * An array that is used to convert internal column numbers to external 723 * external column numbers. 724 * IntToExtRowMap (int []) 725 * An array that is used to convert internal row numbers to external 726 * external row numbers. 727 * MarkowitzCol (int []) 728 * An array that contains the count of the non-zero elements excluding 729 * the pivots for each column. Used to generate and update MarkowitzProd. 730 * MarkowitzProd (long []) 731 * The array of the products of the Markowitz row and column counts. The 732 * element with the smallest product is the best pivot to use to maintain 733 * sparsity. 734 * MarkowitzRow (int []) 735 * An array that contains the count of the non-zero elements excluding 736 * the pivots for each row. Used to generate and update MarkowitzProd. 737 * MaxRowCountInLowerTri (int) 738 * The maximum number of off-diagonal element in the rows of L, the 739 * lower triangular matrix. This quantity is used when computing an 740 * estimate of the roundoff error in the matrix. 741 * NeedsOrdering (BOOLEAN) 742 * This is a flag that signifies that the matrix needs to be ordered 743 * or reordered. NeedsOrdering is set true in spCreate() and 744 * spGetElement() or spGetAdmittance() if new elements are added to the 745 * matrix after it has been previously factored. It is set false in 746 * spOrderAndFactor(). 747 * NumberOfInterchangesIsOdd (BOOLEAN) 748 * Flag that indicates the sum of row and column interchange counts 749 * is an odd number. Used when determining the sign of the determinant. 750 * Partitioned (BOOLEAN) 751 * This flag indicates that the columns of the matrix have been 752 * partitioned into two groups. Those that will be addressed directly 753 * and those that will be addressed indirectly in spFactor(). 754 * PivotsOriginalCol (int) 755 * Column pivot was chosen from. 756 * PivotsOriginalRow (int) 757 * Row pivot was chosen from. 758 * PivotSelectionMethod (char) 759 * Character that indicates which pivot search method was successful. 760 * PreviousMatrixWasComplex (BOOLEAN) 761 * This flag in needed to determine how to clear the matrix. When 762 * dealing with real matrices, it is important that the imaginary terms 763 * in the matrix elements be zero. Thus, if the previous matrix was 764 * complex, then the current matrix will be cleared as if it were complex 765 * even if it is real. 766 * RelThreshold (RealNumber) 767 * The magnitude an element must have relative to others in its row 768 * to be considered as a pivot candidate, except as a last resort. 769 * Reordered (BOOLEAN) 770 * This flag signifies that the matrix has been reordered. It 771 * is cleared in spCreate(), set in spMNA_Preorder() and 772 * spOrderAndFactor() and is used in spPrint(). 773 * RowsLinked (BOOLEAN) 774 * A flag that indicates whether the row pointers exist. The AddByIndex 775 * routines do not generate the row pointers, which are needed by some 776 * of the other routines, such as spOrderAndFactor() and spScale(). 777 * The row pointers are generated in the function spcLinkRows(). 778 * SingularCol (int) 779 * Normally zero, but if matrix is found to be singular, SingularCol is 780 * assigned the external column number of pivot that was zero. 781 * SingularRow (int) 782 * Normally zero, but if matrix is found to be singular, SingularRow is 783 * assigned the external row number of pivot that was zero. 784 * Singletons (int) 785 * The number of singletons available for pivoting. Note that if row I 786 * and column I both contain singletons, only one of them is counted. 787 * Size (int) 788 * Number of rows and columns in the matrix. Does not change as matrix 789 * is factored. 790 * TrashCan (MatrixElement) 791 * This is a dummy MatrixElement that is used to by the user to stuff 792 * data related to the zero row or column. In other words, when the user 793 * adds an element in row zero or column zero, then the matrix returns 794 * a pointer to TrashCan. In this way the user can have a uniform way 795 * data into the matrix independent of whether a component is connected 796 * to ground. 797 * 798 * >>> The remaining fields are related to memory allocation. 799 * TopOfAllocationList (AllocationListPtr) 800 * Pointer which points to the top entry in a list. The list contains 801 * all the pointers to the segments of memory that have been allocated 802 * to this matrix. This is used when the memory is to be freed on 803 * deallocation of the matrix. 804 * RecordsRemaining (int) 805 * Number of slots left in the list of allocations. 806 * NextAvailElement (ElementPtr) 807 * Pointer to the next available element which has been allocated but as 808 * yet is unused. Matrix elements are allocated in groups of 809 * ELEMENTS_PER_ALLOCATION in order to speed element allocation and 810 * freeing. 811 * ElementsRemaining (int) 812 * Number of unused elements left in last block of elements allocated. 813 * NextAvailFillin (ElementPtr) 814 * Pointer to the next available fill-in which has been allocated but 815 * as yet is unused. Fill-ins are allocated in a group in order to keep 816 * them physically close in memory to the rest of the matrix. 817 * FillinsRemaining (int) 818 * Number of unused fill-ins left in the last block of fill-ins 819 * allocated. 820 * FirstFillinListNode (FillinListNodeStruct *) 821 * A pointer to the head of the linked-list that keeps track of the 822 * lists of fill-ins. 823 * LastFillinListNode (FillinListNodeStruct *) 824 * A pointer to the tail of the linked-list that keeps track of the 825 * lists of fill-ins. 826 */ 827 828 /* Begin `MatrixFrame'. */ 829 struct MatrixFrame 830 { RealNumber AbsThreshold; 831 int AllocatedSize; 832 int AllocatedExtSize; 833 BOOLEAN Complex; 834 int CurrentSize; 835 ArrayOfElementPtrs Diag; 836 BOOLEAN *DoCmplxDirect; 837 BOOLEAN *DoRealDirect; 838 int Elements; 839 int Error; 840 int ExtSize; 841 int *ExtToIntColMap; 842 int *ExtToIntRowMap; 843 BOOLEAN Factored; 844 int Fillins; 845 ArrayOfElementPtrs FirstInCol; 846 ArrayOfElementPtrs FirstInRow; 847 unsigned long ID; 848 RealVector Intermediate; 849 BOOLEAN InternalVectorsAllocated; 850 int *IntToExtColMap; 851 int *IntToExtRowMap; 852 int *MarkowitzRow; 853 int *MarkowitzCol; 854 long *MarkowitzProd; 855 int MaxRowCountInLowerTri; 856 BOOLEAN NeedsOrdering; 857 BOOLEAN NumberOfInterchangesIsOdd; 858 BOOLEAN Partitioned; 859 int PivotsOriginalCol; 860 int PivotsOriginalRow; 861 char PivotSelectionMethod; 862 BOOLEAN PreviousMatrixWasComplex; 863 RealNumber RelThreshold; 864 BOOLEAN Reordered; 865 BOOLEAN RowsLinked; 866 int SingularCol; 867 int SingularRow; 868 int Singletons; 869 int Size; 870 struct MatrixElement TrashCan; 871 872 AllocationListPtr TopOfAllocationList; 873 int RecordsRemaining; 874 ElementPtr NextAvailElement; 875 int ElementsRemaining; 876 ElementPtr NextAvailFillin; 877 int FillinsRemaining; 878 struct FillinListNodeStruct *FirstFillinListNode; 879 struct FillinListNodeStruct *LastFillinListNode; 880 }; 881 typedef struct MatrixFrame *MatrixPtr; 882