00001 /* 00002 * DATA STRUCTURE && MACRO DEFINITIONS for Sparse. 00003 * 00004 * Author: Advising professor: 00005 * Kenneth S. Kundert Alberto Sangiovanni-Vincentelli 00006 * UC Berkeley 00007 * 00008 * This file contains common type definitions and macros for the sparse 00009 * matrix routines. These definitions are of no interest to the user. 00010 * 00011 * Revision and copyright information. 00012 * 00013 * Copyright (c) 1985,86,87,88 00014 * by Kenneth S. Kundert and the University of California. 00015 * 00016 * Permission to use, copy, modify, and distribute this software and 00017 * its documentation for any purpose and without fee is hereby granted, 00018 * provided that the copyright notices appear in all copies and 00019 * supporting documentation and that the authors and the University of 00020 * California are properly credited. The authors and the University of 00021 * California make no representations as to the suitability of this 00022 * software for any purpose. It is provided `as is', without express 00023 * or implied warranty. 00024 * 00025 * $Date: 88/06/18 11:13:40 $ 00026 * $Revision: 1.2 $ 00027 */ 00028 00029 #include <stdio.h> 00030 #include <malloc.h> 00031 00032 00033 #ifdef lint 00034 #undef REAL 00035 #undef spCOMPLEX 00036 #undef EXPANDABLE 00037 #undef TRANSLATE 00038 #undef INITIALIZE 00039 #undef DELETE 00040 #undef STRIP 00041 #undef MODIFIED_NODAL 00042 #undef QUAD_ELEMENT 00043 #undef TRANSPOSE 00044 #undef SCALING 00045 #undef DOCUMENTATION 00046 #undef MULTIPLICATION 00047 #undef DETERMINANT 00048 #undef CONDITION 00049 #undef PSEUDOCONDITION 00050 #undef FORTRAN 00051 #undef DEBUG 00052 00053 #define REAL YES 00054 #define spCOMPLEX NO /* YES */ 00055 #define EXPANDABLE NO /* YES */ 00056 #define TRANSLATE NO /* YES */ 00057 #define INITIALIZE YES 00058 #define DELETE YES 00059 #define STRIP YES 00060 #define MODIFIED_NODAL YES 00061 #define QUAD_ELEMENT YES 00062 #define TRANSPOSE NO /* YES */ 00063 #define SCALING YES 00064 #define DOCUMENTATION YES 00065 #define MULTIPLICATION YES 00066 #define DETERMINANT YES 00067 #define CONDITION YES 00068 #define PSEUDOCONDITION YES 00069 #define FORTRAN NO /* YES */ 00070 #define DEBUG YES 00071 00072 #define LINT YES 00073 #else /* not lint */ 00074 #define LINT NO 00075 #endif /* not lint */ 00076 00077 #define BOOLEAN int 00078 00079 #define SPARSE_ID 0x772773 /* Arbitrary (is Sparse on phone). */ 00080 #define IS_SPARSE(matrix) ((matrix) != NULL && (matrix)->ID == SPARSE_ID) 00081 #define IS_VALID(matrix) ((matrix) != NULL && (matrix)->ID == SPARSE_ID && (matrix)->Error >= spOKAY && (matrix)->Error < spFATAL) 00082 #define IS_FACTORED(matrix) ((matrix)->Factored && !(matrix)->NeedsOrdering) 00083 #define MAX(a,b) ((a) > (b) ? (a) : (b)) 00084 #define MIN(a,b) ((a) < (b) ? (a) : (b)) 00085 00086 /* Macro function that returns the absolute value of a floating point number. */ 00087 #define ABSS(a) ((a) < 0.0 ? -(a) : (a)) 00088 00089 /* Macro function that returns the square of a number. */ 00090 #define SQR(a) ((a)*(a)) 00091 00092 /* Macro procedure that swaps two entities. */ 00093 #define SWAP(type, a, b) {type swapx; swapx = a; a = b; b = swapx;} 00094 00095 /* Macro function that returns the approx absolute value of a complex number. */ 00096 #if spCOMPLEX 00097 #define ELEMENT_MAG(ptr) (ABSS((ptr)->Real) + ABSS((ptr)->Imag)) 00098 #else 00099 #define ELEMENT_MAG(ptr) ((ptr)->Real < 0.0 ? -(ptr)->Real : (ptr)->Real) 00100 #endif 00101 00102 /* Complex assignment statements. */ 00103 #define CMPLX_ASSIGN(to,from) { (to).Real = (from).Real; (to).Imag = (from).Imag; } 00104 #define CMPLX_CONJ_ASSIGN(to,from) { (to).Real = (from).Real; (to).Imag = -(from).Imag; } 00105 #define CMPLX_NEGATE_ASSIGN(to,from) { (to).Real = -(from).Real; (to).Imag = -(from).Imag; } 00106 #define CMPLX_CONJ_NEGATE_ASSIGN(to,from) { (to).Real = -(from).Real; (to).Imag = (from).Imag; } 00107 #define CMPLX_CONJ(a) (a).Imag = -(a).Imag 00108 #define CMPLX_NEGATE(a) { (a).Real = -(a).Real; (a).Imag = -(a).Imag; } 00109 00110 /* Macro that returns the approx magnitude (L-1 norm) of a complex number. */ 00111 #define CMPLX_1_NORM(a) (ABSS((a).Real) + ABSS((a).Imag)) 00112 00113 /* Macro that returns the approx magnitude (L-infinity norm) of a complex. */ 00114 #define CMPLX_INF_NORM(a) (MAX (ABSS((a).Real),ABSS((a).Imag))) 00115 00116 /* Macro function that returns the magnitude (L-2 norm) of a complex number. */ 00117 #define CMPLX_2_NORM(a) (sqrt((a).Real*(a).Real + (a).Imag*(a).Imag)) 00118 00119 /* Macro function that performs complex addition. */ 00120 #define CMPLX_ADD(to,from_a,from_b) { (to).Real = (from_a).Real + (from_b).Real; (to).Imag = (from_a).Imag + (from_b).Imag; } 00121 00122 /* Macro function that performs complex subtraction. */ 00123 #define CMPLX_SUBT(to,from_a,from_b) { (to).Real = (from_a).Real - (from_b).Real; (to).Imag = (from_a).Imag - (from_b).Imag; } 00124 00125 /* Macro function that is equivalent to += operator for complex numbers. */ 00126 #define CMPLX_ADD_ASSIGN(to,from) { (to).Real += (from).Real; (to).Imag += (from).Imag; } 00127 00128 /* Macro function that is equivalent to -= operator for complex numbers. */ 00129 #define CMPLX_SUBT_ASSIGN(to,from) { (to).Real -= (from).Real; (to).Imag -= (from).Imag; } 00130 00131 /* Macro function that multiplies a complex number by a scalar. */ 00132 #define SCLR_MULT(to,sclr,cmplx) { (to).Real = (sclr) * (cmplx).Real; (to).Imag = (sclr) * (cmplx).Imag; } 00133 00134 /* Macro function that multiply-assigns a complex number by a scalar. */ 00135 #define SCLR_MULT_ASSIGN(to,sclr) { (to).Real *= (sclr); (to).Imag *= (sclr); } 00136 00137 /* Macro function that multiplies two complex numbers. */ 00138 #define CMPLX_MULT(to,from_a,from_b) { (to).Real = (from_a).Real * (from_b).Real - \ 00139 (from_a).Imag * (from_b).Imag; (to).Imag = (from_a).Real * (from_b).Imag + (from_a).Imag * (from_b).Real; } 00140 00141 /* Macro function that implements to *= from for complex numbers. */ 00142 #define CMPLX_MULT_ASSIGN(to,from) { double to_real_ = (to).Real; \ 00143 (to).Real = to_real_ * (from).Real - (to).Imag * (from).Imag; \ 00144 (to).Imag = to_real_ * (from).Imag + (to).Imag * (from).Real; } 00145 00146 /* Macro function that multiplies two complex numbers, the first of which is 00147 * conjugated. */ 00148 #define CMPLX_CONJ_MULT(to,from_a,from_b) { (to).Real = (from_a).Real * (from_b).Real + \ 00149 (from_a).Imag * (from_b).Imag; (to).Imag = (from_a).Real * (from_b).Imag - (from_a).Imag * (from_b).Real; } 00150 00151 /* Macro function that multiplies two complex numbers and then adds them 00152 * to another. to = add + mult_a * mult_b */ 00153 #define CMPLX_MULT_ADD(to,mult_a,mult_b,add) \ 00154 { (to).Real = (mult_a).Real * (mult_b).Real - \ 00155 (mult_a).Imag * (mult_b).Imag + (add).Real; \ 00156 (to).Imag = (mult_a).Real * (mult_b).Imag + \ 00157 (mult_a).Imag * (mult_b).Real + (add).Imag; \ 00158 } 00159 00160 /* Macro function that subtracts the product of two complex numbers from 00161 * another. to = subt - mult_a * mult_b */ 00162 #define CMPLX_MULT_SUBT(to,mult_a,mult_b,subt) \ 00163 { (to).Real = (subt).Real - (mult_a).Real * (mult_b).Real + (mult_a).Imag * (mult_b).Imag; \ 00164 (to).Imag = (subt).Imag - (mult_a).Real * (mult_b).Imag - (mult_a).Imag * (mult_b).Real; } 00165 00166 /* Macro function that multiplies two complex numbers and then adds them 00167 * to another. to = add + mult_a* * mult_b where mult_a* represents mult_a 00168 * conjugate. */ 00169 #define CMPLX_CONJ_MULT_ADD(to,mult_a,mult_b,add) \ 00170 { (to).Real = (mult_a).Real * (mult_b).Real + \ 00171 (mult_a).Imag * (mult_b).Imag + (add).Real; \ 00172 (to).Imag = (mult_a).Real * (mult_b).Imag - \ 00173 (mult_a).Imag * (mult_b).Real + (add).Imag; \ 00174 } 00175 00176 /* Macro function that multiplies two complex numbers and then adds them 00177 * to another. to += mult_a * mult_b */ 00178 #define CMPLX_MULT_ADD_ASSIGN(to,from_a,from_b) { (to).Real += (from_a).Real * (from_b).Real - \ 00179 (from_a).Imag * (from_b).Imag; (to).Imag += (from_a).Real * (from_b).Imag + (from_a).Imag * (from_b).Real; } 00180 00181 /* Macro function that multiplies two complex numbers and then subtracts them 00182 * from another. */ 00183 #define CMPLX_MULT_SUBT_ASSIGN(to,from_a,from_b) \ 00184 { (to).Real -= (from_a).Real * (from_b).Real - \ 00185 (from_a).Imag * (from_b).Imag; \ 00186 (to).Imag -= (from_a).Real * (from_b).Imag + \ 00187 (from_a).Imag * (from_b).Real; \ 00188 } 00189 00190 /* Macro function that multiplies two complex numbers and then adds them 00191 * to the destination. to += from_a* * from_b where from_a* represents from_a 00192 * conjugate. */ 00193 #define CMPLX_CONJ_MULT_ADD_ASSIGN(to,from_a,from_b) \ 00194 { (to).Real += (from_a).Real * (from_b).Real + \ 00195 (from_a).Imag * (from_b).Imag; \ 00196 (to).Imag += (from_a).Real * (from_b).Imag - \ 00197 (from_a).Imag * (from_b).Real; \ 00198 } 00199 00200 /* Macro function that multiplies two complex numbers and then subtracts them 00201 * from the destination. to -= from_a* * from_b where from_a* represents from_a 00202 * conjugate. */ 00203 #define CMPLX_CONJ_MULT_SUBT_ASSIGN(to,from_a,from_b) \ 00204 { (to).Real -= (from_a).Real * (from_b).Real + \ 00205 (from_a).Imag * (from_b).Imag; \ 00206 (to).Imag -= (from_a).Real * (from_b).Imag - \ 00207 (from_a).Imag * (from_b).Real; \ 00208 } 00209 00210 /* 00211 * Macro functions that provide complex division. 00212 */ 00213 00214 /* Complex division: to = num / den */ 00215 #define CMPLX_DIV(to,num,den) \ 00216 { double r_, s_; \ 00217 if (((den).Real >= (den).Imag && (den).Real > -(den).Imag) || \ 00218 ((den).Real < (den).Imag && (den).Real <= -(den).Imag)) \ 00219 { r_ = (den).Imag / (den).Real; \ 00220 s_ = (den).Real + r_*(den).Imag; \ 00221 (to).Real = ((num).Real + r_*(num).Imag)/s_; \ 00222 (to).Imag = ((num).Imag - r_*(num).Real)/s_; \ 00223 } \ 00224 else \ 00225 { r_ = (den).Real / (den).Imag; \ 00226 s_ = (den).Imag + r_*(den).Real; \ 00227 (to).Real = (r_*(num).Real + (num).Imag)/s_; \ 00228 (to).Imag = (r_*(num).Imag - (num).Real)/s_; \ 00229 } \ 00230 } 00231 00232 /* Complex division and assignment: num /= den */ 00233 #define CMPLX_DIV_ASSIGN(num,den) \ 00234 { double r_, s_, t_; \ 00235 if (((den).Real >= (den).Imag && (den).Real > -(den).Imag) || \ 00236 ((den).Real < (den).Imag && (den).Real <= -(den).Imag)) \ 00237 { r_ = (den).Imag / (den).Real; \ 00238 s_ = (den).Real + r_*(den).Imag; \ 00239 t_ = ((num).Real + r_*(num).Imag)/s_; \ 00240 (num).Imag = ((num).Imag - r_*(num).Real)/s_; \ 00241 (num).Real = t_; \ 00242 } \ 00243 else \ 00244 { r_ = (den).Real / (den).Imag; \ 00245 s_ = (den).Imag + r_*(den).Real; \ 00246 t_ = (r_*(num).Real + (num).Imag)/s_; \ 00247 (num).Imag = (r_*(num).Imag - (num).Real)/s_; \ 00248 (num).Real = t_; \ 00249 } \ 00250 } 00251 00252 /* Complex reciprocation: to = 1.0 / den */ 00253 #define CMPLX_RECIPROCAL(to,den) \ 00254 { double r_; \ 00255 if (((den).Real >= (den).Imag && (den).Real > -(den).Imag) || \ 00256 ((den).Real < (den).Imag && (den).Real <= -(den).Imag)) \ 00257 { r_ = (den).Imag / (den).Real; \ 00258 (to).Imag = -r_*((to).Real = 1.0/((den).Real + r_*(den).Imag)); \ 00259 } \ 00260 else \ 00261 { r_ = (den).Real / (den).Imag; \ 00262 (to).Real = -r_*((to).Imag = -1.0/((den).Imag + r_*(den).Real));\ 00263 } \ 00264 } 00265 00266 /* 00267 * ASSERT and ABORT 00268 * 00269 * Macro used to assert that if the code is working correctly, then 00270 * a condition must be true. If not, then execution is terminated 00271 * and an error message is issued stating that there is an internal 00272 * error and giving the file and line number. These assertions are 00273 * not evaluated unless the DEBUG flag is true. 00274 */ 00275 00276 #if DEBUG 00277 #define ASSERT(condition) if (!(condition)) ABORT() 00278 #else 00279 #define ASSERT(condition) 00280 #endif 00281 00282 #if DEBUG 00283 #define ABORT() { (void)fflush(stdout); \ 00284 (void)fprintf(stderr, "sparse: panic in file `%s' at line %d.\n", \ 00285 __FILE__, __LINE__); (void)fflush(stderr); \ 00286 abort(); \ 00287 } 00288 #else 00289 #define ABORT() 00290 #endif 00291 00292 #define ALLOC(type,number) ((type *)malloc((unsigned)(sizeof(type)*(number)))) 00293 #define REALLOC(ptr,type,number) ptr = (type *)realloc((char *)ptr,(unsigned)(sizeof(type)*(number))) 00294 #define FREE(ptr) { if ((ptr) != NULL) free((char *)(ptr)); (ptr) = NULL; } 00295 00296 /* Calloc that properly handles allocating a cleared vector. */ 00297 #define CALLOC(ptr,type,number) { int i; if ((ptr = ALLOC(type, number)) != (type *)NULL) \ 00298 for(i=(number)-1;i>=0; i--) ptr[i] = (type)0; } 00299 /* 00300 * COMPLEX NUMBER DATA STRUCTURE 00301 * 00302 * >>> Structure fields: 00303 * Real (double) 00304 * The real portion of the number. Real must be the first 00305 * field in this structure. 00306 * Imag (double) 00307 * The imaginary portion of the number. This field must follow 00308 * immediately after Real. 00309 * 00310 typedef struct { double Real, Imag; } ComplexNumber, *ComplexVector;*/ 00311 00312 /* 00313 * MATRIX ELEMENT DATA STRUCTURE 00314 * 00315 * Every nonzero element in the matrix is stored in a dynamically allocated 00316 * MatrixElement structure. These structures are linked together in an 00317 * orthogonal linked list. Two different MatrixElement structures exist. 00318 * One is used when only real matrices are expected, it is missing an entry 00319 * for imaginary data. The other is used if complex matrices are expected. 00320 * It contains an entry for imaginary data. 00321 * 00322 * >>> Structure fields: 00323 * Real (double) 00324 * The real portion of the value of the element. Real must be the first 00325 * field in this structure. 00326 * Imag (double) 00327 * The imaginary portion of the value of the element. If the matrix 00328 * routines are not compiled to handle complex matrices, then this 00329 * field does not exist. If it exists, it must follow immediately after 00330 * Real. 00331 * Row (int) 00332 * The row number of the element. 00333 * Col (int) 00334 * The column number of the element. 00335 * NextInRow (struct MatrixElement *) 00336 * NextInRow contains a pointer to the next element in the row to the 00337 * right of this element. If this element is the last nonzero in the 00338 * row then NextInRow contains NULL. 00339 * NextInCol (struct MatrixElement *) 00340 * NextInCol contains a pointer to the next element in the column below 00341 * this element. If this element is the last nonzero in the column then 00342 * NextInCol contains NULL. 00343 * pInitInfo (char *) 00344 * Pointer to user data used for initialization of the matrix element. 00345 * Initialized to NULL. 00346 * 00347 * >>> Type definitions: 00348 * ElementPtr 00349 * A pointer to a MatrixElement. 00350 * ArrayOfElementPtrs 00351 * An array of ElementPtrs. Used for FirstInRow, FirstInCol and 00352 * Diag pointer arrays. 00353 */ 00354 struct MatrixElement 00355 { 00356 double Real; 00357 int Row, Col; 00358 struct MatrixElement *NextInRow, *NextInCol; 00359 #if INITIALIZE 00360 double *pInitInfo; 00361 #endif 00362 }; 00363 typedef struct MatrixElement *ElementPtr; 00364 typedef ElementPtr *ArrayOfElementPtrs; 00365 /* 00366 * ALLOCATION DATA STRUCTURE 00367 * 00368 * The sparse matrix routines keep track of all memory that is allocated by 00369 * the operating system so the memory can later be freed. This is done by 00370 * saving the pointers to all the chunks of memory that are allocated to a 00371 * particular matrix in an allocation list. That list is organized as a 00372 * linked list so that it can grow without a priori bounds. 00373 * 00374 * >>> Structure fields: 00375 * AllocatedPtr (char *) 00376 * Pointer to chunk of memory that has been allocated for the matrix. 00377 * NextRecord (struct AllocationRecord *) 00378 * Pointer to the next allocation record. 00379 */ 00380 struct AllocationRecord { char *AllocatedPtr; struct AllocationRecord *NextRecord; }; 00381 typedef struct AllocationRecord *AllocationListPtr; 00382 /* 00383 * FILL-IN LIST DATA STRUCTURE 00384 * 00385 * The sparse matrix routines keep track of all fill-ins separately from 00386 * user specified elements so they may be removed by spStripFills(). Fill-ins 00387 * are allocated in bunched in what is called a fill-in lists. The data 00388 * structure defined below is used to organize these fill-in lists into a 00389 * linked-list. 00390 * 00391 * >>> Structure fields: 00392 * pFillinList (ElementPtr) 00393 * Pointer to a fill-in list, or a bunch of fill-ins arranged contiguously 00394 * in memory. 00395 * NumberOfFillinsInList (int) 00396 * Seems pretty self explanatory to me. 00397 * Next (struct FillinListNodeStruct *) 00398 * Pointer to the next fill-in list structures. 00399 */ 00400 struct FillinListNodeStruct { ElementPtr pFillinList; 00401 int NumberOfFillinsInList; 00402 struct FillinListNodeStruct *Next; 00403 }; 00404 /* 00405 * MATRIX FRAME DATA STRUCTURE 00406 * 00407 * This structure contains all the pointers that support the orthogonal 00408 * linked list that contains the matrix elements. Also included in this 00409 * structure are other numbers and pointers that are used globally by the 00410 * sparse matrix routines and are associated with one particular matrix. 00411 * 00412 * >>> Type definitions: 00413 * MatrixPtr 00414 * A pointer to MatrixFrame. Essentially, a pointer to the matrix. 00415 * 00416 * >>> Structure fields: 00417 * AbsThreshold (double) 00418 * The absolute magnitude an element must have to be considered as a 00419 * pivot candidate, except as a last resort. 00420 * AllocatedExtSize (int) 00421 * The allocated size of the arrays used to translate external row and 00422 * column numbers to their internal values. 00423 * AllocatedSize (int) 00424 * The currently allocated size of the matrix; the size the matrix can 00425 * grow to when EXPANDABLE is set true and AllocatedSize is the largest 00426 * the matrix can get without requiring that the matrix frame be 00427 * reallocated. 00428 * Complex (BOOLEAN) 00429 * The flag which indicates whether the matrix is complex (true) or 00430 * real. 00431 * CurrentSize (int) 00432 * This number is used during the building of the matrix when the 00433 * TRANSLATE option is set true. It indicates the number of internal 00434 * rows and columns that have elements in them. 00435 * Diag (ArrayOfElementPtrs) 00436 * Array of pointers that points to the diagonal elements. 00437 * DoCmplxDirect (BOOLEAN *) 00438 * Array of flags, one for each column in matrix. If a flag is true 00439 * then corresponding column in a complex matrix should be eliminated 00440 * in spFactor() using direct addressing (rather than indirect 00441 * addressing). 00442 * DoRealDirect (BOOLEAN *) 00443 * Array of flags, one for each column in matrix. If a flag is true 00444 * then corresponding column in a real matrix should be eliminated 00445 * in spFactor() using direct addressing (rather than indirect 00446 * addressing). 00447 * Elements (int) 00448 * The number of original elements (total elements minus fill ins) 00449 * present in matrix. 00450 * Error (int) 00451 * The error status of the sparse matrix package. 00452 * ExtSize (int) 00453 * The value of the largest external row or column number encountered. 00454 * ExtToIntColMap (int []) 00455 * An array that is used to convert external columns number to internal 00456 * external column numbers. Present only if TRANSLATE option is set true. 00457 * ExtToIntRowMap (int []) 00458 * An array that is used to convert external row numbers to internal 00459 * external row numbers. Present only if TRANSLATE option is set true. 00460 * Factored (BOOLEAN) 00461 * Indicates if matrix has been factored. This flag is set true in 00462 * spFactor() and spOrderAndFactor() and set false in spCreate() 00463 * and spClear(). 00464 * Fillins (int) 00465 * The number of fill-ins created during the factorization the matrix. 00466 * FirstInCol (ArrayOfElementPtrs) 00467 * Array of pointers that point to the first nonzero element of the 00468 * column corresponding to the index. 00469 * FirstInRow (ArrayOfElementPtrs) 00470 * Array of pointers that point to the first nonzero element of the row 00471 * corresponding to the index. 00472 * ID (unsigned long int) 00473 * A constant that provides the sparse data structure with a signature. 00474 * When DEBUG is true, all externally available sparse routines check 00475 * this signature to assure they are operating on a valid matrix. 00476 * Intermediate (double) 00477 * Temporary storage used in the spSolve routines. Intermediate is an 00478 * array used during forward and backward substitution. It is 00479 * commonly called y when the forward and backward substitution process is 00480 * denoted Ax = b => Ly = b and Ux = y. 00481 * InternalVectorsAllocated (BOOLEAN) 00482 * A flag that indicates whether the markowitz vectors and the 00483 * Intermediate vector have been created. 00484 * These vectors are created in CreateInternalVectors(). 00485 * IntToExtColMap (int []) 00486 * An array that is used to convert internal column numbers to external 00487 * external column numbers. 00488 * IntToExtRowMap (int []) 00489 * An array that is used to convert internal row numbers to external 00490 * external row numbers. 00491 * MarkowitzCol (int []) 00492 * An array that contains the count of the non-zero elements excluding 00493 * the pivots for each column. Used to generate and update MarkowitzProd. 00494 * MarkowitzProd (long []) 00495 * The array of the products of the Markowitz row and column counts. The 00496 * element with the smallest product is the best pivot to use to maintain 00497 * sparsity. 00498 * MarkowitzRow (int []) 00499 * An array that contains the count of the non-zero elements excluding 00500 * the pivots for each row. Used to generate and update MarkowitzProd. 00501 * MaxRowCountInLowerTri (int) 00502 * The maximum number of off-diagonal element in the rows of L, the 00503 * lower triangular matrix. This quantity is used when computing an 00504 * estimate of the roundoff error in the matrix. 00505 * NeedsOrdering (BOOLEAN) 00506 * This is a flag that signifies that the matrix needs to be ordered 00507 * or reordered. NeedsOrdering is set true in spCreate() and 00508 * spGetElement() or spGetAdmittance() if new elements are added to the 00509 * matrix after it has been previously factored. It is set false in 00510 * spOrderAndFactor(). 00511 * NumberOfInterchangesIsOdd (BOOLEAN) 00512 * Flag that indicates the sum of row and column interchange counts 00513 * is an odd number. Used when determining the sign of the determinant. 00514 * Partitioned (BOOLEAN) 00515 * This flag indicates that the columns of the matrix have been 00516 * partitioned into two groups. Those that will be addressed directly 00517 * and those that will be addressed indirectly in spFactor(). 00518 * PivotsOriginalCol (int) 00519 * Column pivot was chosen from. 00520 * PivotsOriginalRow (int) 00521 * Row pivot was chosen from. 00522 * PivotSelectionMethod (char) 00523 * Character that indicates which pivot search method was successful. 00524 * PreviousMatrixWasComplex (BOOLEAN) 00525 * This flag in needed to determine how to clear the matrix. When 00526 * dealing with real matrices, it is important that the imaginary terms 00527 * in the matrix elements be zero. Thus, if the previous matrix was 00528 * complex, then the current matrix will be cleared as if it were complex 00529 * even if it is real. 00530 * RelThreshold (double) 00531 * The magnitude an element must have relative to others in its row 00532 * to be considered as a pivot candidate, except as a last resort. 00533 * Reordered (BOOLEAN) 00534 * This flag signifies that the matrix has been reordered. It 00535 * is cleared in spCreate(), set in spMNA_Preorder() and 00536 * spOrderAndFactor() and is used in spPrint(). 00537 * RowsLinked (BOOLEAN) 00538 * A flag that indicates whether the row pointers exist. The AddByIndex 00539 * routines do not generate the row pointers, which are needed by some 00540 * of the other routines, such as spOrderAndFactor() and spScale(). 00541 * The row pointers are generated in the function spcLinkRows(). 00542 * SingularCol (int) 00543 * Normally zero, but if matrix is found to be singular, SingularCol is 00544 * assigned the external column number of pivot that was zero. 00545 * SingularRow (int) 00546 * Normally zero, but if matrix is found to be singular, SingularRow is 00547 * assigned the external row number of pivot that was zero. 00548 * Singletons (int) 00549 * The number of singletons available for pivoting. Note that if row I 00550 * and column I both contain singletons, only one of them is counted. 00551 * Size (int) 00552 * Number of rows and columns in the matrix. Does not change as matrix 00553 * is factored. 00554 * TrashCan (MatrixElement) 00555 * This is a dummy MatrixElement that is used to by the user to stuff 00556 * data related to the zero row or column. In other words, when the user 00557 * adds an element in row zero or column zero, then the matrix returns 00558 * a pointer to TrashCan. In this way the user can have a uniform way 00559 * data into the matrix independent of whether a component is connected 00560 * to ground. 00561 * 00562 * >>> The remaining fields are related to memory allocation. 00563 * TopOfAllocationList (AllocationListPtr) 00564 * Pointer which points to the top entry in a list. The list contains 00565 * all the pointers to the segments of memory that have been allocated 00566 * to this matrix. This is used when the memory is to be freed on 00567 * deallocation of the matrix. 00568 * RecordsRemaining (int) 00569 * Number of slots left in the list of allocations. 00570 * NextAvailElement (ElementPtr) 00571 * Pointer to the next available element which has been allocated but as 00572 * yet is unused. Matrix elements are allocated in groups of 00573 * ELEMENTS_PER_ALLOCATION in order to speed element allocation and 00574 * freeing. 00575 * ElementsRemaining (int) 00576 * Number of unused elements left in last block of elements allocated. 00577 * NextAvailFillin (ElementPtr) 00578 * Pointer to the next available fill-in which has been allocated but 00579 * as yet is unused. Fill-ins are allocated in a group in order to keep 00580 * them physically close in memory to the rest of the matrix. 00581 * FillinsRemaining (int) 00582 * Number of unused fill-ins left in the last block of fill-ins 00583 * allocated. 00584 * FirstFillinListNode (FillinListNodeStruct *) 00585 * A pointer to the head of the linked-list that keeps track of the 00586 * lists of fill-ins. 00587 * LastFillinListNode (FillinListNodeStruct *) 00588 * A pointer to the tail of the linked-list that keeps track of the 00589 * lists of fill-ins. 00590 */ 00591 struct MatrixFrame 00592 { 00593 double AbsThreshold; 00594 int AllocatedSize; 00595 int AllocatedExtSize; 00596 BOOLEAN Complex; 00597 int CurrentSize; 00598 ArrayOfElementPtrs Diag; 00599 BOOLEAN *DoCmplxDirect; 00600 BOOLEAN *DoRealDirect; 00601 int Elements; 00602 int Error; 00603 int ExtSize; 00604 int *ExtToIntColMap; 00605 int *ExtToIntRowMap; 00606 BOOLEAN Factored; 00607 int Fillins; 00608 ArrayOfElementPtrs FirstInCol, FirstInRow; 00609 unsigned long ID; 00610 double* Intermediate; 00611 BOOLEAN InternalVectorsAllocated; 00612 int *IntToExtColMap; 00613 int *IntToExtRowMap; 00614 int *MarkowitzRow; 00615 int *MarkowitzCol; 00616 long *MarkowitzProd; 00617 int MaxRowCountInLowerTri; 00618 BOOLEAN NeedsOrdering; 00619 BOOLEAN NumberOfInterchangesIsOdd; 00620 BOOLEAN Partitioned; 00621 int PivotsOriginalCol; 00622 int PivotsOriginalRow; 00623 char PivotSelectionMethod; 00624 BOOLEAN PreviousMatrixWasComplex; 00625 double RelThreshold; 00626 BOOLEAN Reordered; 00627 BOOLEAN RowsLinked; 00628 int SingularCol; 00629 int SingularRow; 00630 int Singletons; 00631 int Size; 00632 struct MatrixElement TrashCan; 00633 AllocationListPtr TopOfAllocationList; 00634 int RecordsRemaining; 00635 ElementPtr NextAvailElement; 00636 int ElementsRemaining; 00637 ElementPtr NextAvailFillin; 00638 int FillinsRemaining; 00639 struct FillinListNodeStruct *FirstFillinListNode, *LastFillinListNode; 00640 }; 00641 typedef struct MatrixFrame *MatrixPtr;