1 /* 2 * CONFIGURATION MACRO DEFINITIONS for sparse matrix routines 3 * 4 * Author: Advising professor: 5 * Kenneth S. Kundert Alberto Sangiovanni-Vincentelli 6 * U.C. Berkeley 7 * 8 * This file contains macros for the sparse matrix routines that are used 9 * to define the personality of the routines. The user is expected to 10 * modify this file to maximize the performance of the routines with 11 * his/her matrices. 12 * 13 * Macros are distinguished by using solely capital letters in their 14 * identifiers. This contrasts with C defined identifiers which are 15 * strictly lower case, and program variable and procedure names which use 16 * both upper and lower case. 17 */ 18 19 20 /* 21 * Revision and copyright information. 22 * 23 * Copyright (c) 1985,86,87,88,89,90 24 * by Kenneth S. Kundert and the University of California. 25 * 26 * Permission to use, copy, modify, and distribute this software and 27 * its documentation for any purpose and without fee is hereby granted, 28 * provided that the copyright notices appear in all copies and 29 * supporting documentation and that the authors and the University of 30 * California are properly credited. The authors and the University of 31 * California make no representations as to the suitability of this 32 * software for any purpose. It is provided `as is', without express 33 * or implied warranty. 34 * 35 * $Date: 88/06/24 05:00:58 $ 36 * $Revision: 1.3 $ 37 */ 38 39 40 #ifndef spCONFIG_DEFS 41 #define spCONFIG_DEFS 42 43 44 45 46 #ifdef spINSIDE_SPARSE 47 /* 48 * OPTIONS 49 * 50 * These are compiler options. Set each option to one to compile that 51 * section of the code. If a feature is not desired, set the macro 52 * to NO. Recommendations are given in brackets, [ignore them]. 53 * 54 * >>> Option descriptions: 55 * Arithmetic Precision 56 * The precision of the arithmetic used by Sparse can be set by 57 * changing changing the spREAL macro. This macro is 58 * contained in the file spMatrix.h. It is strongly suggested to 59 * used double precision with circuit simulators. Note that 60 * because C always performs arithmetic operations in double 61 * precision, the only benefit to using single precision is that 62 * less storage is required. There is often a noticeable speed 63 * penalty when using single precision. Sparse internally refers 64 * to a spREAL as a RealNumber. 65 * REAL 66 * This specifies that the routines are expected to handle real 67 * systems of equations. The routines can be compiled to handle 68 * both real and complex systems at the same time, but there is a 69 * slight speed and memory advantage if the routines are complied 70 * to handle only real systems of equations. 71 * spCOMPLEX 72 * This specifies that the routines will be complied to handle 73 * complex systems of equations. 74 * EXPANDABLE 75 * Setting this compiler flag true (1) makes the matrix 76 * expandable before it has been factored. If the matrix is 77 * expandable, then if an element is added that would be 78 * considered out of bounds in the current matrix, the size of 79 * the matrix is increased to hold that element. As a result, 80 * the size of the matrix need not be known before the matrix is 81 * built. The matrix can be allocated with size zero and 82 * expanded. 83 * TRANSLATE 84 * This option allows the set of external row and column numbers 85 * to be non-packed. In other words, the row and column numbers 86 * do not have to be contiguous. The priced paid for this 87 * flexibility is that when TRANSLATE is set true, the time 88 * required to initially build the matrix will be greater because 89 * the external row and column number must be translated into 90 * internal equivalents. This translation brings about other 91 * benefits though. First, the spGetElement() and 92 * spGetAdmittance() routines may be used after the matrix has 93 * been factored. Further, elements, and even rows and columns, 94 * may be added to the matrix, and row and columns may be deleted 95 * from the matrix, after it has been factored. Note that when 96 * the set of row and column number is not a packed set, neither 97 * are the RHS and Solution vectors. Thus the size of these 98 * vectors must be at least as large as the external size, which 99 * is the value of the largest given row or column numbers. 100 * INITIALIZE 101 * Causes the spInitialize(), spGetInitInfo(), and 102 * spInstallInitInfo() routines to be compiled. These routines 103 * allow the user to store and read one pointer in each nonzero 104 * element in the matrix. spInitialize() then calls a user 105 * specified function for each structural nonzero in the matrix, 106 * and includes this pointer as well as the external row and 107 * column numbers as arguments. This allows the user to write 108 * custom matrix initialization routines. 109 * DIAGONAL_PIVOTING 110 * Many matrices, and in particular node- and modified-node 111 * admittance matrices, tend to be nearly symmetric and nearly 112 * diagonally dominant. For these matrices, it is a good idea to 113 * select pivots from the diagonal. With this option enabled, 114 * this is exactly what happens, though if no satisfactory pivot 115 * can be found on the diagonal, an off-diagonal pivot will be 116 * used. If this option is disabled, Sparse does not 117 * preferentially search the diagonal. Because of this, Sparse 118 * has a wider variety of pivot candidates available, and so 119 * presumably fewer fill-ins will be created. However, the 120 * initial pivot selection process will take considerably longer. 121 * If working with node admittance matrices, or other matrices 122 * with a strong diagonal, it is probably best to use 123 * DIAGONAL_PIVOTING for two reasons. First, accuracy will be 124 * better because pivots will be chosen from the large diagonal 125 * elements, thus reducing the chance of growth. Second, a near 126 * optimal ordering will be chosen quickly. If the class of 127 * matrices you are working with does not have a strong diagonal, 128 * do not use DIAGONAL_PIVOTING, but consider using a larger 129 * threshold. When DIAGONAL_PIVOTING is turned off, the following 130 * options and constants are not used: MODIFIED_MARKOWITZ, 131 * MAX_MARKOWITZ_TIES, and TIES_MULTIPLIER. 132 * ARRAY_OFFSET 133 * This determines whether arrays start at an index of zero or one. 134 * This option is necessitated by the fact that standard C 135 * convention dictates that arrays begin with an index of zero but 136 * the standard mathematic convention states that arrays begin with 137 * an index of one. So if you prefer to start your arrays with 138 * zero, or your calling Sparse from FORTRAN, set ARRAY_OFFSET to 139 * NO or 0. Otherwise, set ARRAY_OFFSET to YES or 1. Note that if 140 * you use an offset of one, the arrays that you pass to Sparse 141 * must have an allocated length of one plus the size of the 142 * matrix. ARRAY_OFFSET must be either 0 or 1, no other offsets 143 * are valid. 144 * spSEPARATED_COMPLEX_VECTORS 145 * This specifies the format for complex vectors. If this is set 146 * false then a complex vector is made up of one double sized 147 * array of RealNumber's in which the real and imaginary numbers 148 * are placed in the alternately array in the array. In other 149 * words, the first entry would be Complex[1].Real, then comes 150 * Complex[1].Imag, then Complex[1].Real, etc. If 151 * spSEPARATED_COMPLEX_VECTORS is set true, then each complex 152 * vector is represented by two arrays of RealNumbers, one with 153 * the real terms, the other with the imaginary. [NO] 154 * MODIFIED_MARKOWITZ 155 * This specifies that the modified Markowitz method of pivot 156 * selection is to be used. The modified Markowitz method differs 157 * from standard Markowitz in two ways. First, under modified 158 * Markowitz, the search for a pivot can be terminated early if a 159 * adequate (in terms of sparsity) pivot candidate is found. 160 * Thus, when using modified Markowitz, the initial factorization 161 * can be faster, but at the expense of a suboptimal pivoting 162 * order that may slow subsequent factorizations. The second 163 * difference is in the way modified Markowitz breaks Markowitz 164 * ties. When two or more elements are pivot candidates and they 165 * all have the same Markowitz product, then the tie is broken by 166 * choosing the element that is best numerically. The numerically 167 * best element is the one with the largest ratio of its magnitude 168 * to the magnitude of the largest element in the same column, 169 * excluding itself. The modified Markowitz method results in 170 * marginally better accuracy. This option is most appropriate 171 * for use when working with very large matrices where the initial 172 * factor time represents an unacceptable burden. [NO] 173 * DELETE 174 * This specifies that the spDeleteRowAndCol() routine 175 * should be compiled. Note that for this routine to be 176 * compiled, both DELETE and TRANSLATE should be set true. 177 * STRIP 178 * This specifies that the spStripFills() routine should be compiled. 179 * MODIFIED_NODAL 180 * This specifies that the routine that preorders modified node 181 * admittance matrices should be compiled. This routine results 182 * in greater speed and accuracy if used with this type of 183 * matrix. 184 * QUAD_ELEMENT 185 * This specifies that the routines that allow four related 186 * elements to be entered into the matrix at once should be 187 * compiled. These elements are usually related to an 188 * admittance. The routines affected by QUAD_ELEMENT are the 189 * spGetAdmittance, spGetQuad and spGetOnes routines. 190 * TRANSPOSE 191 * This specifies that the routines that solve the matrix as if 192 * it was transposed should be compiled. These routines are 193 * useful when performing sensitivity analysis using the adjoint 194 * method. 195 * SCALING 196 * This specifies that the routine that performs scaling on the 197 * matrix should be complied. Scaling is not strongly 198 * supported. The routine to scale the matrix is provided, but 199 * no routines are provided to scale and descale the RHS and 200 * Solution vectors. It is suggested that if scaling is desired, 201 * it only be preformed when the pivot order is being chosen [in 202 * spOrderAndFactor()]. This is the only time scaling has 203 * an effect. The scaling may then either be removed from the 204 * solution by the user or the scaled factors may simply be 205 * thrown away. [NO] 206 * DOCUMENTATION 207 * This specifies that routines that are used to document the 208 * matrix, such as spPrint() and spFileMatrix(), should be 209 * compiled. 210 * DETERMINANT 211 * This specifies that the routine spDeterminant() should be complied. 212 * STABILITY 213 * This specifies that spLargestElement() and spRoundoff() should 214 * be compiled. These routines are used to check the stability (and 215 * hence the quality of the pivoting) of the factorization by 216 * computing a bound on the size of the element is the matrix E = 217 * A - LU. If this bound is very high after applying 218 * spOrderAndFactor(), then the pivot threshold should be raised. 219 * If the bound increases greatly after using spFactor(), then the 220 * matrix should probably be reordered. 221 * CONDITION 222 * This specifies that spCondition() and spNorm(), the code that 223 * computes a good estimate of the condition number of the matrix, 224 * should be compiled. 225 * PSEUDOCONDITION 226 * This specifies that spPseudoCondition(), the code that computes 227 * a crude and easily fooled indicator of ill-conditioning in the 228 * matrix, should be compiled. 229 * MULTIPLICATION 230 * This specifies that the routines to multiply the unfactored 231 * matrix by a vector should be compiled. 232 * FORTRAN 233 * This specifies that the FORTRAN interface routines should be 234 * compiled. When interfacing to FORTRAN programs, the ARRAY_OFFSET 235 * options should be set to NO. 236 * DEBUG 237 * This specifies that additional error checking will be compiled. 238 * The type of error checked are those that are common when the 239 * matrix routines are first integrated into a user's program. Once 240 * the routines have been integrated in and are running smoothly, this 241 * option should be turned off. 242 * spCOMPATIBILITY 243 * This specifies that Sparse1.3 should be configured to be upward 244 * compatible from Sparse1.2. This option is not suggested for use 245 * in new software. Sparse1.3, when configured to be compatible with 246 * Sparse1.2, is not completely compatible. In particular, if 247 * recompiling the calling program, it is necessary to change the 248 * of the Sparse include files. This option will go away in future 249 * versions of Sparse. [0] 250 */ 251 252 /* Begin options. */ 253 #define REAL YES 254 #define EXPANDABLE YES 255 #define TRANSLATE YES 256 #define INITIALIZE NO 257 #define DIAGONAL_PIVOTING YES 258 #define ARRAY_OFFSET YES 259 #define MODIFIED_MARKOWITZ NO 260 #define DELETE NO 261 #define STRIP NO 262 #define MODIFIED_NODAL YES 263 #define QUAD_ELEMENT NO 264 #define TRANSPOSE YES 265 #define SCALING NO 266 #define DOCUMENTATION YES 267 #define MULTIPLICATION YES 268 #define DETERMINANT YES 269 #define DETERMINANT2 YES 270 #define STABILITY NO 271 #define CONDITION NO 272 #define PSEUDOCONDITION NO 273 #define FORTRAN NO 274 /* SRW - DEBUG set to YES in UCB distribution */ 275 #define DEBUG NO 276 277 /* 278 * The following options affect Sparse exports and so are exported as a 279 * side effect. For this reason they use the `sp' prefix. The boolean 280 * constants YES an NO are not defined in spMatrix.h to avoid conflicts 281 * with user code, so use 0 for NO and 1 for YES. 282 */ 283 #endif /* spINSIDE_SPARSE */ 284 #define spCOMPLEX 1 285 #define spSEPARATED_COMPLEX_VECTORS 1 286 #define spCOMPATIBILITY 0 287 #ifdef spINSIDE_SPARSE 288 289 290 291 292 293 294 295 /* 296 * MATRIX CONSTANTS 297 * 298 * These constants are used throughout the sparse matrix routines. They 299 * should be set to suit the type of matrix being solved. Recommendations 300 * are given in brackets. 301 * 302 * Some terminology should be defined. The Markowitz row count is the number 303 * of non-zero elements in a row excluding the one being considered as pivot. 304 * There is one Markowitz row count for every row. The Markowitz column 305 * is defined similarly for columns. The Markowitz product for an element 306 * is the product of its row and column counts. It is a measure of how much 307 * work would be required on the next step of the factorization if that 308 * element were chosen to be pivot. A small Markowitz product is desirable. 309 * 310 * >>> Constants descriptions: 311 * DEFAULT_THRESHOLD 312 * The relative threshold used if the user enters an invalid 313 * threshold. Also the threshold used by spFactor() when 314 * calling spOrderAndFactor(). The default threshold should 315 * not be less than or equal to zero nor larger than one. [0.001] 316 * DIAG_PIVOTING_AS_DEFAULT 317 * This indicates whether spOrderAndFactor() should use diagonal 318 * pivoting as default. This issue only arises when 319 * spOrderAndFactor() is called from spFactor(). 320 * SPACE_FOR_ELEMENTS 321 * This number multiplied by the size of the matrix equals the number 322 * of elements for which memory is initially allocated in 323 * spCreate(). [6] 324 * SPACE_FOR_FILL_INS 325 * This number multiplied by the size of the matrix equals the number 326 * of elements for which memory is initially allocated and specifically 327 * reserved for fill-ins in spCreate(). [4] 328 * ELEMENTS_PER_ALLOCATION 329 * The number of matrix elements requested from the malloc utility on 330 * each call to it. Setting this value greater than 1 reduces the 331 * amount of overhead spent in this system call. On a virtual memory 332 * machine, its good to allocate slightly less than a page worth of 333 * elements at a time (or some multiple thereof). 334 * [For the VAX, for real only use 41, otherwise use 31] 335 * MINIMUM_ALLOCATED_SIZE 336 * The minimum allocated size of a matrix. Note that this does not 337 * limit the minimum size of a matrix. This just prevents having to 338 * resize a matrix many times if the matrix is expandable, large and 339 * allocated with an estimated size of zero. This number should not 340 * be less than one. 341 * EXPANSION_FACTOR 342 * The amount the allocated size of the matrix is increased when it 343 * is expanded. 344 * MAX_MARKOWITZ_TIES 345 * This number is used for two slightly different things, both of which 346 * relate to the search for the best pivot. First, it is the maximum 347 * number of elements that are Markowitz tied that will be sifted 348 * through when trying to find the one that is numerically the best. 349 * Second, it creates an upper bound on how large a Markowitz product 350 * can be before it eliminates the possibility of early termination 351 * of the pivot search. In other words, if the product of the smallest 352 * Markowitz product yet found and TIES_MULTIPLIER is greater than 353 * MAX_MARKOWITZ_TIES, then no early termination takes place. 354 * Set MAX_MARKOWITZ_TIES to some small value if no early termination of 355 * the pivot search is desired. An array of RealNumbers is allocated 356 * of size MAX_MARKOWITZ_TIES so it must be positive and shouldn't 357 * be too large. Active when MODIFIED_MARKOWITZ is 1 (true). [100] 358 * TIES_MULTIPLIER 359 * Specifies the number of Markowitz ties that are allowed to occur 360 * before the search for the pivot is terminated early. Set to some 361 * large value if no early termination of the pivot search is desired. 362 * This number is multiplied times the Markowitz product to determine 363 * how many ties are required for early termination. This means that 364 * more elements will be searched before early termination if a large 365 * number of fill-ins could be created by accepting what is currently 366 * considered the best choice for the pivot. Active when 367 * MODIFIED_MARKOWITZ is 1 (true). Setting this number to zero 368 * effectively eliminates all pivoting, which should be avoided. 369 * This number must be positive. TIES_MULTIPLIER is also used when 370 * diagonal pivoting breaks down. [5] 371 * DEFAULT_PARTITION 372 * Which partition mode is used by spPartition() as default. 373 * Possibilities include 374 * spDIRECT_PARTITION -- each row used direct addressing, best for 375 * a few relatively dense matrices. 376 * spINDIRECT_PARTITION -- each row used indirect addressing, best 377 * for a few very sparse matrices. 378 * spAUTO_PARTITION -- direct or indirect addressing is chosen on 379 * a row-by-row basis, carries a large overhead, but speeds up 380 * both dense and sparse matrices, best if there is a large 381 * number of matrices that can use the same ordering. 382 */ 383 384 /* Begin constants. */ 385 #define DEFAULT_THRESHOLD 1.0e-3 386 #define DIAG_PIVOTING_AS_DEFAULT YES 387 #define SPACE_FOR_ELEMENTS 6 388 #define SPACE_FOR_FILL_INS 4 389 #define ELEMENTS_PER_ALLOCATION 31 390 #define MINIMUM_ALLOCATED_SIZE 6 391 #define EXPANSION_FACTOR 1.5 392 #define MAX_MARKOWITZ_TIES 100 393 #define TIES_MULTIPLIER 5 394 #define DEFAULT_PARTITION spAUTO_PARTITION 395 396 397 398 399 400 401 /* 402 * PRINTER WIDTH 403 * 404 * This macro characterize the printer for the spPrint() routine. 405 * 406 * >>> Macros: 407 * PRINTER_WIDTH 408 * The number of characters per page width. Set to 80 for terminal, 409 * 132 for line printer. 410 */ 411 412 /* Begin printer constants. */ 413 #define PRINTER_WIDTH 80 414 415 416 417 418 419 420 /* 421 * MACHINE CONSTANTS 422 * 423 * These numbers must be updated when the program is ported to a new machine. 424 */ 425 426 /* Begin machine constants. */ 427 428 /* 429 * Grab from Spice include files 430 */ 431 432 #include "spice.h" 433 #define MACHINE_RESOLUTION DBL_EPSILON 434 #define LARGEST_REAL DBL_MAX 435 #define SMALLEST_REAL DBL_MIN 436 #define LARGEST_SHORT_INTEGER SHRT_MAX 437 #define LARGEST_LONG_INTEGER LONG_MAX 438 439 440 /* 441 * ANNOTATION 442 * 443 * This macro changes the amount of annotation produced by the matrix 444 * routines. The annotation is used as a debugging aid. Change the number 445 * associated with ANNOTATE to change the amount of annotation produced by 446 * the program. 447 */ 448 449 /* Begin annotation definitions. */ 450 #define ANNOTATE NONE 451 452 #define NONE 0 453 #define ON_STRANGE_BEHAVIOR 1 454 #define FULL 2 455 456 #endif /* spINSIDE_SPARSE */ 457 #endif /* spCONFIG_DEFS */ 458