00001 /* 00002 * CONFIGURATION MACRO DEFINITIONS for sparse matrix routines 00003 * 00004 * Author: Advising professor: 00005 * Kenneth S. Kundert Alberto Sangiovanni-Vincentelli 00006 * U.C. Berkeley 00007 * 00008 * This file contains macros for the sparse matrix routines that are used 00009 * to define the personality of the routines. The user is expected to 00010 * modify this file to maximize the performance of the routines with 00011 * his/her matrices. 00012 * 00013 * Macros are distinguished by using solely capital letters in their 00014 * identifiers. This contrasts with C defined identifiers which are 00015 * strictly lower case, and program variable and procedure names which use 00016 * both upper and lower case. 00017 */ 00018 00019 00020 /* 00021 * Revision and copyright information. 00022 * 00023 * Copyright (c) 1985,86,87,88 00024 * by Kenneth S. Kundert and the University of California. 00025 * 00026 * Permission to use, copy, modify, and distribute this software and 00027 * its documentation for any purpose and without fee is hereby granted, 00028 * provided that the copyright notices appear in all copies and 00029 * supporting documentation and that the authors and the University of 00030 * California are properly credited. The authors and the University of 00031 * California make no representations as to the suitability of this 00032 * software for any purpose. It is provided `as is', without express 00033 * or implied warranty. 00034 * 00035 * $Date: 88/06/18 11:13:29 $ 00036 * $Revision: 1.2 $ 00037 */ 00038 00039 00040 #ifndef spCONFIG_DEFS 00041 #define spCONFIG_DEFS 00042 00043 #ifdef spINSIDE_SPARSE 00044 /* 00045 * OPTIONS 00046 * 00047 * These are compiler options. Set each option to one to compile that 00048 * section of the code. If a feature is not desired, set the macro 00049 * to 0. Recommendations are given in brackets, [ignore them]. 00050 * 00051 * >>> Option descriptions: 00052 * Arithmetic Precision 00053 * The precision of the arithmetic used by Sparse can be set by 00054 * changing changing the double macro. This macro is 00055 * contained in the file spMatrix.h. It is strongly suggested to 00056 * used double precision with circuit simulators. Note that 00057 * because C always performs arithmetic operations in double 00058 * precision, the only benefit to using single precision is that 00059 * less storage is required. There is often a noticeable speed 00060 * penalty when using single precision. Sparse internally refers 00061 * to a double as a RealNumber. 00062 * REAL 00063 * This specifies that the routines are expected to handle real 00064 * systems of equations. The routines can be compiled to handle 00065 * both real and complex systems at the same time, but there is a 00066 * slight speed and memory advantage if the routines are complied 00067 * to handle only real systems of equations. 00068 * spCOMPLEX 00069 * This specifies that the routines will be complied to handle 00070 * complex systems of equations. 00071 * EXPANDABLE 00072 * Setting this compiler flag true (1) makes the matrix 00073 * expandable before it has been factored. If the matrix is 00074 * expandable, then if an element is added that would be 00075 * considered out of bounds in the current matrix, the size of 00076 * the matrix is increased to hold that element. As a result, 00077 * the size of the matrix need not be known before the matrix is 00078 * built. The matrix can be allocated with size zero and 00079 * expanded. 00080 * TRANSLATE 00081 * This option allows the set of external row and column numbers 00082 * to be non-packed. In other words, the row and column numbers 00083 * do not have to be contiguous. The priced paid for this 00084 * flexibility is that when TRANSLATE is set true, the time 00085 * required to initially build the matrix will be greater because 00086 * the external row and column number must be translated into 00087 * internal equivalents. This translation brings about other 00088 * benefits though. First, the spGetElement() and 00089 * spGetAdmittance() routines may be used after the matrix has 00090 * been factored. Further, elements, and even rows and columns, 00091 * may be added to the matrix, and row and columns may be deleted 00092 * from the matrix, after it has been factored. Note that when 00093 * the set of row and column number is not a packed set, neither 00094 * are the RHS and Solution vectors. Thus the size of these 00095 * vectors must be at least as large as the external size, which 00096 * is the value of the largest given row or column numbers. 00097 * INITIALIZE 00098 * Causes the spInitialize(), spGetInitInfo(), and 00099 * spInstallInitInfo() routines to be compiled. These routines 00100 * allow the user to store and read one pointer in each nonzero 00101 * element in the matrix. spInitialize() then calls a user 00102 * specified function for each structural nonzero in the matrix, 00103 * and includes this pointer as well as the external row and 00104 * column numbers as arguments. This allows the user to write 00105 * custom matrix initialization routines. 00106 * DIAGONAL_PIVOTING 00107 * Many matrices, and in particular node- and modified-node 00108 * admittance matrices, tend to be nearly symmetric and nearly 00109 * diagonally dominant. For these matrices, it is a good idea to 00110 * select pivots from the diagonal. With this option enabled, 00111 * this is exactly what happens, though if no satisfactory pivot 00112 * can be found on the diagonal, an off-diagonal pivot will be 00113 * used. If this option is disabled, Sparse does not 00114 * preferentially search the diagonal. Because of this, Sparse 00115 * has a wider variety of pivot candidates available, and so 00116 * presumably fewer fill-ins will be created. However, the 00117 * initial pivot selection process will take considerably longer. 00118 * If working with node admittance matrices, or other matrices 00119 * with a strong diagonal, it is probably best to use 00120 * DIAGONAL_PIVOTING for two reasons. First, accuracy will be 00121 * better because pivots will be chosen from the large diagonal 00122 * elements, thus reducing the chance of growth. Second, a near 00123 * optimal ordering will be chosen quickly. If the class of 00124 * matrices you are working with does not have a strong diagonal, 00125 * do not use DIAGONAL_PIVOTING, but consider using a larger 00126 * threshold. When DIAGONAL_PIVOTING is turned off, the following 00127 * options and constants are not used: MODIFIED_MARKOWITZ, 00128 * MAX_MARKOWITZ_TIES, and TIES_MULTIPLIER. 00129 * ARRAY_OFFSET 00130 * This determines whether arrays start at an index of zero or one. 00131 * This option is necessitated by the fact that standard C 00132 * convention dictates that arrays begin with an index of zero but 00133 * the standard mathematic convention states that arrays begin with 00134 * an index of one. So if you prefer to start your arrays with 00135 * zero, or your calling Sparse from FORTRAN, set ARRAY_OFFSET to 00136 * 0 or 0. Otherwise, set ARRAY_OFFSET to 1 or 1. Note that if 00137 * you use an offset of one, the arrays that you pass to Sparse 00138 * must have an allocated length of one plus the size of the 00139 * matrix. ARRAY_OFFSET must be either 0 or 1, no other offsets 00140 * are valid. 00141 * spSEPARATED_COMPLEX_VECTORS 00142 * This specifies the format for complex vectors. If this is set 00143 * false then a complex vector is made up of one double sized 00144 * array of RealNumber's in which the real and imaginary numbers 00145 * are placed in the alternately array in the array. In other 00146 * words, the first entry would be Complex[1].Real, then comes 00147 * Complex[1].Imag, then Complex[1].Real, etc. If 00148 * spSEPARATED_COMPLEX_VECTORS is set true, then each complex 00149 * vector is represented by two arrays of RealNumbers, one with 00150 * the real terms, the other with the imaginary. [0] 00151 * MODIFIED_MARKOWITZ 00152 * This specifies that the modified Markowitz method of pivot 00153 * selection is to be used. The modified Markowitz method differs 00154 * from standard Markowitz in two ways. First, under modified 00155 * Markowitz, the search for a pivot can be terminated early if a 00156 * adequate (in terms of sparsity) pivot candidate is found. 00157 * Thus, when using modified Markowitz, the initial factorization 00158 * can be faster, but at the expense of a suboptimal pivoting 00159 * order that may slow subsequent factorizations. The second 00160 * difference is in the way modified Markowitz breaks Markowitz 00161 * ties. When two or more elements are pivot candidates and they 00162 * all have the same Markowitz product, then the tie is broken by 00163 * choosing the element that is best numerically. The numerically 00164 * best element is the one with the largest ratio of its magnitude 00165 * to the magnitude of the largest element in the same column, 00166 * excluding itself. The modified Markowitz method results in 00167 * marginally better accuracy. This option is most appropriate 00168 * for use when working with very large matrices where the initial 00169 * factor time represents an unacceptable burden. [0] 00170 * DELETE 00171 * This specifies that the spDeleteRowAndCol() routine 00172 * should be compiled. Note that for this routine to be 00173 * compiled, both DELETE and TRANSLATE should be set true. 00174 * STRIP 00175 * This specifies that the spStripFills() routine should be compiled. 00176 * MODIFIED_NODAL 00177 * This specifies that the routine that preorders modified node 00178 * admittance matrices should be compiled. This routine results 00179 * in greater speed and accuracy if used with this type of 00180 * matrix. 00181 * QUAD_ELEMENT 00182 * This specifies that the routines that allow four related 00183 * elements to be entered into the matrix at once should be 00184 * compiled. These elements are usually related to an 00185 * admittance. The routines affected by QUAD_ELEMENT are the 00186 * spGetAdmittance, spGetQuad and spGetOnes routines. 00187 * TRANSPOSE 00188 * This specifies that the routines that solve the matrix as if 00189 * it was transposed should be compiled. These routines are 00190 * useful when performing sensitivity analysis using the adjoint 00191 * method. 00192 * SCALING 00193 * This specifies that the routine that performs scaling on the 00194 * matrix should be complied. Scaling is not strongly 00195 * supported. The routine to scale the matrix is provided, but 00196 * no routines are provided to scale and descale the RHS and 00197 * Solution vectors. It is suggested that if scaling is desired, 00198 * it only be preformed when the pivot order is being chosen [in 00199 * spOrderAndFactor()]. This is the only time scaling has 00200 * an effect. The scaling may then either be removed from the 00201 * solution by the user or the scaled factors may simply be 00202 * thrown away. [0] 00203 * DOCUMENTATION 00204 * This specifies that routines that are used to document the 00205 * matrix, such as spPrint() and spFileMatrix(), should be 00206 * compiled. 00207 * DETERMINANT 00208 * This specifies that the routine spDeterminant() should be complied. 00209 * STABILITY 00210 * This specifies that spLargestElement() and spRoundoff() should 00211 * be compiled. These routines are used to check the stability (and 00212 * hence the quality of the pivoting) of the factorization by 00213 * computing a bound on the size of the element is the matrix E = 00214 * A - LU. If this bound is very high after applying 00215 * spOrderAndFactor(), then the pivot threshold should be raised. 00216 * If the bound increases greatly after using spFactor(), then the 00217 * matrix should probably be reordered. 00218 * CONDITION 00219 * This specifies that spCondition() and spNorm(), the code that 00220 * computes a good estimate of the condition number of the matrix, 00221 * should be compiled. 00222 * PSEUDOCONDITION 00223 * This specifies that spPseudoCondition(), the code that computes 00224 * a crude and easily fooled indicator of ill-conditioning in the 00225 * matrix, should be compiled. 00226 * MULTIPLICATION 00227 * This specifies that the routines to multiply the unfactored 00228 * matrix by a vector should be compiled. 00229 * FORTRAN 00230 * This specifies that the FORTRAN interface routines should be 00231 * compiled. When interfacing to FORTRAN programs, the ARRAY_OFFSET 00232 * options should be set to 0. 00233 * DEBUG 00234 * This specifies that additional error checking will be compiled. 00235 * The type of error checked are those that are common when the 00236 * matrix routines are first integrated into a user's program. Once 00237 * the routines have been integrated in and are running smoothly, this 00238 * option should be turned off. 00239 */ 00240 #define REAL 1 00241 #define EXPANDABLE 1 00242 #define TRANSLATE 0 00243 #define INITIALIZE 0 00244 #define DIAGONAL_PIVOTING 1 00245 #define ARRAY_OFFSET 0 /*!FORTRAN*/ 00246 #define MODIFIED_MARKOWITZ 0 00247 #define DELETE 1 00248 #define STRIP 1 00249 #define MODIFIED_NODAL 1 00250 #define QUAD_ELEMENT 1 00251 #define TRANSPOSE 1 00252 #define SCALING 1 00253 #define DOCUMENTATION 1 00254 #define MULTIPLICATION 1 00255 #define DETERMINANT 1 00256 #define STABILITY 1 00257 #define CONDITION 1 00258 #define PSEUDOCONDITION 1 00259 #define FORTRAN 0 00260 #define DEBUG 1 00261 /* 00262 * The following options affect Sparse exports and so are exported as a 00263 * side effect. For this reason they use the `sp' prefix. The boolean 00264 * constants 1 an 0 are not defined in spMatrix.h to avoid conflicts 00265 * with user code, so use 0 for 0 and 1 for 1. 00266 */ 00267 #endif /* spINSIDE_SPARSE */ 00268 #define spCOMPLEX 0/********** 1 *******/ 00269 #define spSEPARATED_COMPLEX_VECTORS 0 00270 #ifdef spINSIDE_SPARSE 00271 /* 00272 * MATRIX CONSTANTS 00273 * 00274 * These constants are used throughout the sparse matrix routines. They 00275 * should be set to suit the type of matrix being solved. Recommendations 00276 * are given in brackets. 00277 * 00278 * Some terminology should be defined. The Markowitz row count is the number 00279 * of non-zero elements in a row excluding the one being considered as pivot. 00280 * There is one Markowitz row count for every row. The Markowitz column 00281 * is defined similarly for columns. The Markowitz product for an element 00282 * is the product of its row and column counts. It is a measure of how much 00283 * work would be required on the next step of the factorization if that 00284 * element were chosen to be pivot. A small Markowitz product is desirable. 00285 * 00286 * >>> Constants descriptions: 00287 * DEFAULT_THRESHOLD 00288 * The relative threshold used if the user enters an invalid 00289 * threshold. Also the threshold used by spFactor() when 00290 * calling spOrderAndFactor(). The default threshold should 00291 * not be less than or equal to zero nor larger than one. [0.001] 00292 * DIAG_PIVOTING_AS_DEFAULT 00293 * This indicates whether spOrderAndFactor() should use diagonal 00294 * pivoting as default. This issue only arises when 00295 * spOrderAndFactor() is called from spFactor(). 00296 * SPACE_FOR_ELEMENTS 00297 * This number multiplied by the size of the matrix equals the number 00298 * of elements for which memory is initially allocated in 00299 * spCreate(). [6] 00300 * SPACE_FOR_FILL_INS 00301 * This number multiplied by the size of the matrix equals the number 00302 * of elements for which memory is initially allocated and specifically 00303 * reserved for fill-ins in spCreate(). [4] 00304 * ELEMENTS_PER_ALLOCATION 00305 * The number of matrix elements requested from the malloc utility on 00306 * each call to it. Setting this value greater than 1 reduces the 00307 * amount of overhead spent in this system call. On a virtual memory 00308 * machine, its good to allocate slightly less than a page worth of 00309 * elements at a time (or some multiple thereof). 00310 * [For the VAX, for real only use 41, otherwise use 31] 00311 * MINIMUM_ALLOCATED_SIZE 00312 * The minimum allocated size of a matrix. Note that this does not 00313 * limit the minimum size of a matrix. This just prevents having to 00314 * resize a matrix many times if the matrix is expandable, large and 00315 * allocated with an estimated size of zero. This number should not 00316 * be less than one. 00317 * EXPANSION_FACTOR 00318 * The amount the allocated size of the matrix is increased when it 00319 * is expanded. 00320 * MAX_MARKOWITZ_TIES 00321 * This number is used for two slightly different things, both of which 00322 * relate to the search for the best pivot. First, it is the maximum 00323 * number of elements that are Markowitz tied that will be sifted 00324 * through when trying to find the one that is numerically the best. 00325 * Second, it creates an upper bound on how large a Markowitz product 00326 * can be before it eliminates the possibility of early termination 00327 * of the pivot search. In other words, if the product of the smallest 00328 * Markowitz product yet found and TIES_MULTIPLIER is greater than 00329 * MAX_MARKOWITZ_TIES, then no early termination takes place. 00330 * Set MAX_MARKOWITZ_TIES to some small value if no early termination of 00331 * the pivot search is desired. An array of RealNumbers is allocated 00332 * of size MAX_MARKOWITZ_TIES so it must be positive and shouldn't 00333 * be too large. Active when MODIFIED_MARKOWITZ is 1 (true). [100] 00334 * TIES_MULTIPLIER 00335 * Specifies the number of Markowitz ties that are allowed to occur 00336 * before the search for the pivot is terminated early. Set to some 00337 * large value if no early termination of the pivot search is desired. 00338 * This number is multiplied times the Markowitz product to determine 00339 * how many ties are required for early termination. This means that 00340 * more elements will be searched before early termination if a large 00341 * number of fill-ins could be created by accepting what is currently 00342 * considered the best choice for the pivot. Active when 00343 * MODIFIED_MARKOWITZ is 1 (true). Setting this number to zero 00344 * effectively eliminates all pivoting, which should be avoided. 00345 * This number must be positive. TIES_MULTIPLIER is also used when 00346 * diagonal pivoting breaks down. [5] 00347 * DEFAULT_PARTITION 00348 * Which partition mode is used by spPartition() as default. 00349 * Possibilities include 00350 * spDIRECT_PARTITION -- each row used direct addressing, best for 00351 * a few relatively dense matrices. 00352 * spINDIRECT_PARTITION -- each row used indirect addressing, best 00353 * for a few very sparse matrices. 00354 * spAUTO_PARTITION -- direct or indirect addressing is chosen on 00355 * a row-by-row basis, carries a large overhead, but speeds up 00356 * both dense and sparse matrices, best if there is a large 00357 * number of matrices that can use the same ordering. 00358 */ 00359 #define DEFAULT_THRESHOLD 1.0e-3 00360 #define DIAG_PIVOTING_AS_DEFAULT 1 00361 #define SPACE_FOR_ELEMENTS 6 00362 #define SPACE_FOR_FILL_INS 4 00363 #define ELEMENTS_PER_ALLOCATION 31 00364 #define MINIMUM_ALLOCATED_SIZE 6 00365 #define EXPANSION_FACTOR 1.5 00366 #define MAX_MARKOWITZ_TIES 100 00367 #define TIES_MULTIPLIER 5 00368 #define DEFAULT_PARTITION spAUTO_PARTITION 00369 /* 00370 * PRINTER WIDTH 00371 * 00372 * This macro characterize the printer for the spPrint() routine. 00373 * 00374 * >>> Macros: 00375 * PRINTER_WIDTH 00376 * The number of characters per page width. Set to 80 for terminal, 00377 * 132 for line printer. 00378 */ 00379 #define PRINTER_WIDTH 80 00380 #include <stdlib.h> 00381 #include <limits.h> 00382 #include <float.h> 00383 /* 00384 * ANNOTATION 00385 * 00386 * This macro changes the amount of annotation produced by the matrix 00387 * routines. The annotation is used as a debugging aid. Change the number 00388 * associated with ANNOTATE to change the amount of annotation produced by 00389 * the program. 00390 */ 00391 #define ANNOTATE NONE 00392 #define NONE 0 00393 #define ON_STRANGE_BEHAVIOR 1 00394 #define FULL 2 00395 00396 #endif /* spINSIDE_SPARSE */ 00397 #endif /* spCONFIG_DEFS */