.LP .pn 1 .if t .nr PS 11 .if t .nr VS 13 .if t .po 1.5i .if t .nr PO 1.5i .if n .ll 7.5i .if n .nr LL 7.5i .rs .ls 1 .\ .\ .\ >>> Revision information: .\ $Author: kundert $ .\ $Date: 88/06/18 11:17:55 $ .\ $Revision: 1.2 $ .\ .\ .\ Define registers for section and subsection .nr sc 0 1 .nr ss 0 1 .\ .\ .\ Define macro for separating procedure descriptions .de Lb .KS .nf .ta 6i .tc \(ru .tc .LP .sp 0.3v .ta 6iR \s+2\fB\\n(sc.\\n+(ss:\ \ \\$1(\|)\fR\s-2 \" \s+4\fI\\$1()\fR\s-4 .ta 0.5i .LP .. .de Le .LP .ta 6i .tc \(ru .tc .KE .sp 0.3v .. .EQ delim $$ gsize 11 tdefine norm % \^ \(br fwd 10 \(br % ndefine norm % || % ndefine delta % d % ndefine epsilon % e % ndefine kappa % K % .EN .hw SEP-AR-ATED_-COM-PLEX_-VEC-TORS .\ .\ .\ Begin the document .ps 24 .sp 1.75i .ce .B "Sparse User's Guide" .ps .sp .2i .LG .LG .LG .I .ce 1 A Sparse Linear Equation Solver .NL .NL .R .sp 0.25i .ce Version 1.3a .sp .05i .ce 1 1 April 1988 .NL .sp 0.75i .R .LG .R .ce 2 .I "Kenneth S. Kundert" .I "Alberto Sangiovanni-Vincentelli" .sp 1.0i .ce 4 Department of .sp 0.25v Electrical Engineering and Computer Sciences .sp 0.25v University of California, Berkeley .sp 0.25v Berkeley, Calif. 94720 .NL .bp .RT .ne 1i .LG .B "\n+(sc: INTRODUCTION" .NL .XS \n% \" Save section title for table of contents \n(sc: Introduction .XE .PP \fISparse1.3\fP is a flexible package of subroutines written in C used to quickly and accurately solve large sparse systems of linear equations. The package is able to handle arbitrary real and complex square matrix equations. Besides being able to solve linear systems, it is also able to quickly solve transposed systems, find determinants, and estimate errors due to ill-conditioning in the system of equations and instability in the computations. \fISparse\fR also provides a test program that is able read matrix equations from a file, solve them, and print useful information about the equation and its solution. .PP \fISparse1.3\fR is generally as fast or faster than other popular sparse matrix packages when solving many matrices of similar structure. \fISparse\fR does not require or assume symmetry and is able to perform numerical pivoting to avoid unnecessary error in the solution. It handles its own memory allocation, which allows the user to forgo the hassle of providing adequate memory. It also has a natural, flexible, and efficient interface to the calling program. .PP \fISparse\fR was originally written for use in circuit simulators and is particularly apt at handling node- and modified-node admittance matrices. The systems of linear generated in a circuit simulator stem from solving large systems of nonlinear equations using Newton's method and integrating large stiff systems of ordinary differential equations. However, \fISparse\fR is also suitable for other uses, one in particular is solving the very large systems of linear equations resulting from the numerical solution of partial differential equations. .sp 2 .RT .ne 1i .LG .B "\n(sc.\n+(ss: Features of Sparse1.3" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Features of Sparse1.3 .XE .PP Beyond the basic capability of being able to create, factor and solve systems of equations, this package features several other capabilities that enhance its utility. These features are: .IP \(bu Ability to handle both real and complex systems of equations. Both types may resident and active at the same time. In fact, the same matrix may alternate between being real and complex. .IP \(bu Ability to quickly solve the transposed system. This feature is useful when computing the sensitivity of a circuit using the adjoint method. .IP \(bu Memory for elements in the matrix is allocated dynamically, so the size of the matrix is only limited by the amount of memory available to \fISparse\fP and the range of the integer data type, which is used to hold matrix indices. .IP \(bu Ability to efficiently compute the condition number of the matrix and an a posteriori estimate of the error caused by growth in the size of the elements during the factorization. .IP \(bu Much of the matrix initialization can be performed by \fISparse\fP, providing advantages in speed and simplified coding of the calling program. .IP \(bu Ability to preorder modified node admittance matrices to enhance accuracy and speed. .IP \(bu Ability to exploit sparsity in the right-hand side vector to reduce unnecessary computation. .IP \(bu Ability to scale matrices prior to factoring to reduce uncertainty in the solution. .IP \(bu The ability to create and build a matrix without knowing its final size. .IP \(bu The ability to add elements, and rows and columns, to a matrix after the matrix has been reordered. .IP \(bu The ability to delete rows and columns from a matrix. .IP \(bu The ability to strip the fill-ins from a matrix. This can improve the efficiency of a subsequent reordering. .IP \(bu The ability to handle matrices that have rows and columns missing from their input description. .IP \(bu Ability to output the matrix in forms readable by either by people or by the \fISparse\fP package. Basic statistics on the matrix can also be output. .IP \(bu By default all arithmetic operations and number storage use double precision. Thus, \fISparse\fP usually gives accurate results, even on highly ill-conditioned systems. If so desired, \fISparse\fP can be easily configured to use single precision arithmetic. .sp 2 .RT .ne 1i .LG .B "\n(sc.\n+(ss: Enhancements of Sparse1.3 over Sparse1.2" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Enhancements of Sparse1.3 over Sparse1.2 .XE .PP Most notable of the enhancements provided by \fISparse1.3\fR is that it is considerably faster on dense matrices. Also, external names have been made unique to 7 characters and the \fISparse\fR prefix \fBsp\fR has been prepended to all externally accessible names to avoid conflicts. In addition, a routine that efficiently estimates the condition number of a matrix has been added and the code that estimates the growth in the factorization has been split off from the actual factorization so that it is computed only when needed. .PP It is now possible for the user program to store information in the matrix elements. It is also possible to provide a subroutine to \fISparse\fP that uses that information to initialize the matrix. This can greatly simplify the user's code. .PP \fISparse1.3\fR has an FORTRAN interface. Routines written in FORTRAN can access almost all of the features \fISparse1.3\fR. .sp 2 .RT .ne 1i .LG .B "\n(sc.\n+(ss: Copyright Information" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Copyright Information .XE .PP \fISparse1.3\fP has been copyrighted. Permission to use, copy, modify, and distribute this software and its documentation for any purpose and without fee is hereby granted, provided that the copyright notice appear in all copies, and \fISparse\fP and the University of California, Berkeley are referenced in all documentation for the program or product in which \fISparse\fP is to be installed. The authors and the University of California make no representations as to the suitability of the software for any purpose. It is provided `as is', without express or implied warranty. .bp .nr ss 0 1 \" Reset subsection .RT .ne 1.5i .LG .B "\n+(sc: PRIMER" .NL .XS \n% \" Save section title for table of contents \n(sc: Primer .XE .sp .RT .LG .B "\n(sc.\n+(ss: Solving Matrix Equations" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Solving Matrix Equations .XE .PP \fISparse\fP contains a collection of C subprograms that can be used to solve linear algebraic systems of equations. These systems are of the form: .EQ I bold { Ax ~=~ b } .EN where $bold A$ is an $n times n$ matrix, $bold x$ is the vector of $n$ unknowns and $bold b$ is the vector of $n$ right-hand side terms. Through out this package $bold A$ is denoted \fIMatrix\fP, $bold x$ is denoted \fISolution\fP and $bold b$ is denoted \fIRHS\fP (for right-hand side). The system is solved using LU factorization, so the actual solution process is broken into two steps, the factorization or decomposition of the matrix, performed by \fIspFactor()\fP, and the forward and backward substitution, performed by \fIspSolve()\fP. \fIspFactor()\fP factors the given matrix into upper and lower triangular matrices independent of the right-hand side. Once this is done, the solution vector can be determined efficiently for any number of right-hand sides without refactoring the matrix. .PP This package exploits the fact that large matrices usually are sparse by not storing or operating on elements in the matrix that are zero. Storing zero elements is avoided by organizing the matrix into an orthogonal linked-list. Thus, to access an element if only its indices are known requires stepping through the list, which is slow. This function is performed by the routine \fIspGetElement()\fP. It is used to initially enter data into a matrix and to build the linked-list. Because it is common to repeatedly solve matrices with identical zero/nonzero structure, it is possible to reuse the linked-list. Thus, the linked list is left in memory and the element values are simply cleared by \fIspClear()\fP before the linked-list is reused. To speed the entering of the element values into successive matrices, \fIspGetElement()\fP returns a pointer to the element in the matrix. This pointer can then be used to place data directly into the matrix without having to traverse through the linked-list. .PP The order in which the rows and columns of the matrix are factored is very important. It directly affects the amount of time required for the factorization and the forward and backward substitution. It also affects the accuracy of the result. The process of choosing this order is time consuming, but fortunately it usually only has to be done once for each particular matrix structure encountered. When a matrix with a new zero/nonzero structure is to be factored, it is done by using \fIspOrderAndFactor()\fP. Subsequent matrices of the same structure are factored with \fIspFactor()\fP. The latter routine does not have the ability to reorder matrix, but it is considerably faster. It may be that a order chosen may be unsuitable for subsequent factorizations. If this is known to be true a priori, it is possible to use \fIspOrderAndFactor()\fP for the subsequent factorizations, with a noticeable speed penalty. \fIspOrderAndFactor()\fP monitors the numerical stability of the factorization and will modify an existing ordering to maintain stability. Otherwise, an a posteriori measure of the numerical stability of the factorization can be computed, and the matrix reordered if necessary. .PP The \fISparse\fP routines allow several matrices of different structures to be resident at once. When a matrix of a new structure is encountered, the user calls \fIspCreate()\fP. This routine creates the basic frame for the linked-list and returns a pointer to this frame. This pointer is then passed as an argument to the other \fISparse\fP routines to indicate which matrix is to be operated on. The number of matrices that can be kept in memory at once is only limited by the amount of memory available to the user and the size of the matrices. When a matrix frame is no longer needed, the memory can be reclaimed by calling \fIspDestroy()\fP. .PP A more complete discussion of sparse systems of equations, methods for solving them, their error mechanisms, and the algorithms used in \fISparse\fP can be found in Kundert [kundert86]. A particular emphasis is placed on matrices resulting from circuit simulators. .sp 2 .RT .ne 1i .LG .B "\n(sc.\n+(ss: Error Control" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Error Control .XE .PP There are two separate mechanisms that can cause errors during the factoring and solution of a system of equations. The first is ill-conditioning in the system. A system of equations is ill-conditioned if the solution is excessively sensitive to disturbances in the input data, which occurs when the system is nearly singular. If a system is ill-conditioned then uncertainty in the result is unavoidable, even if $bold A$ is accurately factored into $bold L$ and $bold U$. When ill-conditioning is a problem, the problem as stated is probably ill-posed and the system should be reformulated such that it is not so ill-conditioned. It is possible to measure the ill-conditioning of matrix using \fIspCondition()\fP. This function returns an estimate of the reciprocal of the condition number of the matrix ($kappa ( bold A )$) [strang80]. The condition number can be used when computing a bound on the error in the solution using the following inequality [golub83]. .EQ {norm delta bold x norm} over {norm bold x norm} ~<=~ kappa ( bold A) left ( {norm delta bold A norm} over {norm bold A norm} ~+~ {norm delta bold b norm} over {norm bold b norm} right ) ~+~ "higher order terms" .EN where $delta bold A$ and $delta bold b$ are the uncertainties in the matrix and right-hand side vector and are assumed small. .PP The second mechanism that causes uncertainty is the build up of roundoff error. Roundoff error can become excessive if there is sufficient growth in the size of the elements during the factorization. Growth is controlled by careful pivoting. In \fISparse\fP, the pivoting is controlled by the relative threshold parameter. In conventional full matrix techniques the pivot is chosen to be the largest element in a column. When working with sparse matrices it is important to choose pivots to minimize the reduction in sparsity. The best pivot to retain sparsity is often not the best pivot to retain accuracy. Thus, some compromise must be made. In threshold pivoting, as used in this package, the best pivot to retain sparsity is used unless it is smaller than the relative threshold times the largest element in the column. Thus, a relative threshold close to one emphasizes accuracy so it will produce a minimum amount of growth, unfortunately it also slows the factorization. A very small relative threshold emphasizes maintenance of sparsity and so speeds the factorization, but can result in a large amount of growth. In our experience, we have found that a relative threshold of 0.001 seems to result in a satisfactory compromise between speed and accuracy, though other authors suggest a more conservative value of 0.1 [duff86]. .PP The growth that occurred during a factorization can be computed by taking the ratio of the largest matrix element in any stage of the factorization to the largest matrix element before factorization. The two numbers are estimated using \fIspLargestElement()\fP. If the growth is found to be excessive after \fIspOrderAndFactor()\fP, then the relative threshold should be increased and the matrix reconstructed and refactored. Once the matrix has been ordered and factored without suffering too much growth, the amount of growth that occurred should be recorded. If, on subsequent factorizations, as performed by \fIspFactor()\fP, the amount of growth becomes significantly larger, then the matrix should be reconstructed and reordered using the same relative threshold with \fIspOrderAndFactor()\fP. If the growth is still excessive, then the relative threshold should be raised again. .sp 2 .RT .ne 1i .LG .B "\n(sc.\n+(ss: Building the Matrix" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Building the Matrix .XE .PP It is not necessary to specify the size of the matrix before beginning to add elements to it. When the compiler option EXPANDABLE is turned on it is possible to initially specify the size of the matrix to any size equal to or smaller than the final size of the matrix. Specifically, the matrix size may be initially specified as zero. If this is done then, as the elements are entered into the matrix, the matrix is enlarged as needed. This feature is particularly useful in circuit simulators because it allows the building of the matrix as the circuit description is parsed. Note that once the matrix has been reordered by the routines \fIspMNA_Preorder()\fP, \fIspFactor()\fP or \fIspOrderAndFactor()\fP the size of the matrix becomes fixed and may no longer be enlarged unless the compiler option TRANSLATE is enabled. .PP The TRANSLATE option allows \fISparse\fP to translate a non-packed set of row and column numbers to an internal packed set. In other words, there may be rows and columns missing from the external description of the matrix. This feature provides two benefits. First, if two matrices are identical in structure, except for a few missing rows and columns in one, then the TRANSLATE option allows them to be treated identically. Similarly, rows and columns may be deleted from a matrix after it has been built and operated upon. Deletion of rows and columns is performed by the function \fIspDeleteRowAndCol()\fP. Second, it allows the use of the functions \fIspGetElement()\fP, \fIspGetAdmittance()\fP, \fIspGetQuad()\fP, and \fIspGetOnes()\fP after the matrix has been reordered. These functions access the matrix by using row and column indices, which have to be translated to internal indices once the matrix is reordered. Thus, when TRANSLATE is used in conjunction with the EXPANDABLE option, rows and columns may be added to a matrix after it has been reordered. .PP Another provided feature that is useful with circuit simulators is the ability to add elements to the matrix in row zero or column zero. These elements will have no affect on the matrix or the results. The benefit of this is that when working with a nodal formulation, grounded components do not have to be treated special when building the matrix. .sp 2 .RT .ne 1i .LG .B "\n(sc.\n+(ss: Initializing the Matrix" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Initializing the Matrix .XE .PP Once a matrix has been factored, it is necessary to clear the matrix before it can be reloaded with new values. The straight forward way of doing that is to call \fIspClear()\fP, which sets the value of every element in the matrix to zero. \fISparse\fP also provides a more flexible way to clear the matrix. Using \fIspInitialize()\fP, it is possible to clear and reload at least part of the matrix in one step. .PP \fISparse\fR allows the user to keep initialization information with each structurally nonzero matrix element. Each element has a pointer that is set and used by the user. The user can set this pointer using \fIspInstallInitInfo()\fR and may read it using \fIspGetInitInfo()\fR. The function \fIspInitialize()\fR is a user customizable way to initialize the matrix. Passed to this routine is a function pointer. \fIspInitialize()\fR sweeps through every element in the matrix and checks the \fIpInitInfo\fR pointer (the user supplied pointer). If the \fIpInitInfo\fR is NULL, which is true unless the user changes it (always true for fill-ins), then the element is zeroed. Otherwise, the function pointer is called and passed the \fIpInitInfo\fR pointer as well as the element pointer and the external row and column numbers, allowing the user to initialize the matrix element and the right-hand side. .PP Why \fIspInitialize()\fR would be used over \fIspClear()\fR can be illustrated by way of an example. Consider a circuit simulator that handles linear and nonlinear resistors and capacitors performing a transient analysis. For the linear resistors, a constant value is loaded into the matrix at each time step and for each Newton iteration. For the linear capacitor, a value is loaded into the matrix that is constant over Newton iterations, but is a function of the time step and the integration method. The nonlinear components contribute values to the matrix that change on every time step and Newton iteration. .PP \fISparse\fP allows the user to attach a data structure to each element in the matrix. For this example, the user might attach a structure that held several pieces of information, such as the conductance of the linear resistor, the capacitance of the linear capacitor, the capacitance of the nonlinear capacitor, and perhaps past values of capacitances. The user also provides a subroutine to \fIspInitialize()\fP that is called for each user-created element in the matrix. This routine would, using the information in the attached data structure, initialize the matrix element and perhaps the right-hand side vector. .PP In this example, the user supplied routine might load the linear conductance into the matrix and multiply it by some voltage to find a current that could be loaded into the right-hand side vector. For the capacitors, the routine would first apply an integration method and then load the matrix and the right-hand side. .PP This approach is useful for two reasons. First, much of the work of the device code in the simulator can be off-loaded onto the matrix package. Since there are usually many devices, this usually results overall in a simpler system. Second, the integration method can be hidden from the simulator device code. Thus the integration method can be changed simply by changing the routine handed to \fIspInitialize()\fP, resulting in a much cleaner and more easily maintained simulator. .sp 2 .RT .ne 1i .LG .B "\n(sc.\n+(ss: Indices" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Indices .XE .PP By far the most common errors made when using \fISparse\fR are related to array indices. \fISparse\fR itself contributes to the problem by having several different indexing schemes. There are three different options that affect index bounds or the way indices are interpreted. The first is ARRAY_OFFSET, which only affects array indices. ARRAY_OFFSET is a compiler flag that selects whether arrays start at index zero or index one. Note that if ARRAY_OFFSET is zero then \fIRHS\fP[0] corresponds to row one in the matrix and \fISolution\fP[0] corresponds to column one. Further note that when ARRAY_OFFSET is set to one, then the allocated length of the arrays handed to the \fISparse\fR routines should be at least the external size of the matrix plus one. The main utility of ARRAY_OFFSET is that it allows natural array indexing when \fISparse\fR is coupled to programs in other languages. For example; in FORTRAN arrays always start at one whereas in C array always start at zero. Thus the first entry in a FORTRAN array corresponds to the zero'th entry in a C array. Setting ARRAY_OFFSET to zero allows the arrays in FORTRAN to start at one rather than two. For the rest of this discussion, assume that ARRAY_OFFSET is set so that arrays start at one in the program that calls \fISparse\fR. .sp 0.3v .PP The second option that affects indices is EXPANDABLE. When EXPANDABLE is set false the upper bound on array and matrix indices is \fISize\fP, where \fISize\fP is a parameter handed to \fIspCreate()\fP. When EXPANDABLE set true, then there is essentially no upper bound on array indices. Indeed, the size of the matrix is determined by the largest row or column number handed to \fISparse\fR. The upper bound on the array indices then equals the final size determined by \fISparse\fR. This size can be determined by calling \fIspGetSize()\fP. .sp 0.3v .PP The final option that affects indices is TRANSLATE. This option was provided to allow row and columns to be deleted, but it also allows row and column numbers to be missing from the input description for a matrix. This means that the size of the matrix is not determined by the largest row or column number entered into the matrix. Rather, the size is determined by the total number of rows or column entered. For example, if the elements [2,3], [5,3], and [7,2] are entered into the matrix, the internal size of the matrix becomes four while the external size is seven. The internal size equals the number of rows and columns in the matrix while the external size equals the largest row or column number entered into the matrix. Note that if a row is entered into the matrix, then its corresponding column is also entered, and vice versa. The indices used in the \fIRHS\fP and \fISolution\fP vectors correspond to the row and column indices in the matrix. Thus, for this example, valid data is expected in \fIRHS\fP at locations 2, 3, 5 and 7. Data at other locations is ignored. Similarly, valid data is returned in \fISolution\fP at locations 2, 3, 5, and 7. The other locations are left unmolested. This shows that the length of the arrays correspond to the external size of the matrix. Again, this value can be determined by \fIspGetSize()\fP. .sp 2 .RT .ne 1i .LG .B "\n(sc.\n+(ss: Configuring Sparse" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Configuring Sparse .XE .PP It is possible at compile-time to customize \fISparse\fR for your particular application. This is done by changing the compiler options, which are kept in the personality file, \fBspConfig.h\fP. There are three classes of choices available. First are the \fISparse\fP options, which specify the dominant personality characteristics, such as if real and/or complex systems of equations are to be handled. The second class is the \fISparse\fP constants, such as the default pivot threshold and the amount of memory initially allocated per matrix. The last class is the machine constants. These numbers must be updated when \fISparse\fP is ported to another machine. .PP As an aid in the setup and testing of \fISparse\fP a test routine and several test matrices and their solutions have been provided. The test routine is capable of reading files generated by \fIspFileMatrix()\fP and \fIspFileVector()\fP. .PP By default \fISparse\fP stores all real numbers and performs all computations using double precision arithmetic. This can be changed by changing the definition of \fIspREAL\fP from \fBdouble\fP to \fBfloat\fP. \fIspREAL\fP is defined in \fBspExports.h\fP. .bp .nr ss 0 1 \" Reset subsection .RT .ne 1.5i .LG .B "\n+(sc: INTRODUCTION TO THE SPARSE ROUTINES" .NL .XS \n% \" Save section title for table of contents \n(sc: Introduction to the Sparse Routines .XE .sp In this section the routines are grouped by function and briefly described. .KS .RT .LG .B "\n(sc.\n+(ss: Creating the Matrix" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Creating the Matrix .XE .LP .I spCreate() .RS .br Allocates and initializes the data structure for a matrix. Necessarily the first routine run for any particular matrix. .RE .KE .KS .LP .I spDestroy() .RS .br Destroys the data structure for a matrix and frees the memory. .RE .KE .KS .LP .I spSetReal() .br .I spSetComplex() .RS .br These routines toggle a flag internal to \fISparse\fP that indicates that the matrix is either real or complex. This is useful if both real and complex matrices of identical structure are expected. .RE .KE .sp 2 .KS .RT .LG .B "\n(sc.\n+(ss: Building the Matrix" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Building the Matrix .XE .LP .I spGetElement() .RS .br Assures that the specified element exists in the matrix data structure and returns a pointer to it. .RE .KE .KS .LP .I spGetAdmittance() .br .I spGetQuad() .br .I spGetOnes() .RS .br These routines add a group of four related elements to the matrix. \fIspGetAdmittance()\fP adds the four elements associated with a two terminal admittance. \fIspGetQuad()\fP is a more general routine that is useful for entering controlled sources to the matrix. \fIspGetOnes()\fP adds the four structural ones to the matrix that are often encountered with elements that do not have admittance representations. .RE .KE .KS .LP .I spDeleteRowAndCol() .RS .br This function is used to delete a row and column from the matrix. .RE .KE .sp 2 .KS .RT .LG .B "\n(sc.\n+(ss: Clearing the Matrix" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Clearing the Matrix .XE .LP .I spClear() .RS .br Sets every element in the matrix to zero. .RE .KE .KS .LP .I spInitialize() .RS .br Runs a user provided initialization routine on each element in the matrix. This routine would be used in lieu of \fIspClear()\fR. .RE .KE .KS .LP .I spGetInitInfo() .br .I spInstallInitInfo() .RS .br These routines allow the user to install and read a user-provided pointer to initialization data for a particular matrix element. .RE .KE .KS .LP .I spStripFills() .RS .br This routine returns a matrix to a semi-virgin state by removing all fill-ins. This can be useful if a matrix is to be reordered and it has changed significantly since it was previously ordered. This may be the case if a few rows and columns have been added or deleted or if the previous ordering was done on a matrix that was numerically quite different than the matrix currently being factored. Stripping and reordering a matrix may speed subsequent factorization if the current ordering is inferior, whereas simply reordering will generally only enhance accuracy and not speed. .RE .KE .sp 2 .KS .RT .LG .B "\n(sc.\n+(ss: Placing Data in the Matrix" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Placing Data in the Matrix .XE .LP .I spADD_REAL_ELEMENT() .br .I spADD_IMAG_ELEMENT() .br .I spADD_COMPLEX_ELEMENT() .RS .br Adds a value to a particular matrix element. .RE .KE .KS .LP .I spADD_REAL_QUAD() .br .I spADD_IMAG_QUAD() .br .I spADD_COMPLEX_QUAD() .RS .br Adds a value to a group of four matrix elements. .RE .KE .sp 2 .KS .RT .LG .B "\n(sc.\n+(ss: Influencing the Factorization" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Influencing the Factorization .XE .LP .I spMNA_Preorder() .RS .br This routine preorders modified node admittance matrices so that \fISparse\fP can take full advantage of their structure. In particular, this routine tries to remove zeros from the diagonal so that diagonal pivoting can be used more successfully. .RE .KE .KS .LP .I spPartition() .RS .br \fISparse\fR partitions the matrix in an attempt to make \fIspFactor()\fP run as fast as possible. The partitioning is a relatively expensive operation that is not needed in all cases. \fIspPartition()\fR allows the user specify a simpler and faster partitioning. .RE .KE .KS .LP .I spScale() .br .RS It is sometimes desirable to scale the rows and columns of a matrix in to achieve a better pivoting order. This is particularly true in modified node admittance matrices, where the size of the elements in a matrix can easily vary through ten to twelve orders of magnitude. This routine performs scaling on a matrix. .RE .KE .sp 2 .RT .ne 1i .LG .B "\n(sc.\n+(ss: Factoring the Matrix" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Factoring the Matrix .XE .KS .LP .I spOrderAndFactor() .RS .br This routine chooses a pivot order for the matrix and factors it into LU form. It handles both the initial factorization and subsequent factorizations when a reordering is desired. .RE .KE .KS .LP .I spFactor() .RS .br Factors a matrix that has already been ordered by \fIspOrderAndFactor()\fR. If \fIspFactor()\fR is passed a matrix that needs ordering, it will automatically pass the matrix to \fIspOrderAndFactor()\fR. .RE .KE .sp 2 .KS .RT .ne 1i .LG .B "\n(sc.\n+(ss: Solving the Matrix Equation" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Solving the Matrix Equation .XE .LP .I spSolve() .br .RS Solves the matrix equation .EQ I bold "A" bold x ~=~ bold b .EN given the matrix $bold A$ factored into LU form and $bold b$. .RE .KE .KS .LP .I spSolveTransposed() .br .RS When working with adjoint systems, such as in sensitivity analysis, it is desirable to quickly solve .EQ I bold "A" sup roman T bold x ~=~ bold b .EN Once $bold A$ has been factored into LU form, this routine can be used to solve the transposed system without having to suffer the cost of factoring the matrix again. .RE .KE .sp 2 .KS .RT .ne 1i .LG .B "\n(sc.\n+(ss: Numerical Error Estimation" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Numerical Error Estimation .XE .LP .I spCondition() .RS .br Estimates the L-infinity condition number of the matrix. This number is a measure of the ill-conditioning in the matrix equation. It is also useful for making estimates of the error in the solution. .RE .KE .KS .LP .I spNorm() .RS .br Returns the L-infinity norm (the maximum absolute row sum) of an unfactored matrix. .RE .KE .KS .LP .I spPseudoCondition() .RS .br Returns the ratio of the largest pivot to the smallest pivot of a factored matrix. This is a rough indicator of ill-conditioning in the matrix. .RE .KE .KS .LP .I spLargestElement() .RS .br If passed an unfactored matrix, this routine returns the absolute value of the largest element in the matrix. If passed a factored matrix, it returns an estimate of the largest element that occurred in any of the reduced submatrices during the factorization. The ratio of these two numbers (factored/unfactored) is the growth, which is used to determine if the pivoting order is numerically satisfactory. .RE .KE .KS .LP .I spRoundoff() .RS .br Returns a bound on the magnitude of the largest element in $bold E ~=~ bold A - bold LU$, where $bold E$ represents error in the matrix resulting from roundoff error during the factorization. .RE .KE .sp 2 .KS .RT .LG .B "\n(sc.\n+(ss: Matrix Operations" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Matrix Operations .XE .LP .I spDeterminant() .RS .br This routine simply calculates and returns the determinant of the factored matrix. .RE .KE .KS .LP .I spMultiply() .br .RS This routine multiplys the matrix by a vector on the right. This is useful for forming the product $ bold "Ax" ~=~ bold b $ in order to determine if a calculated solution is correct. .RE .KE .KS .LP .I spMultTransposed() .br .RS Multiplys the transposed matrix by a vector on the right. This is useful for forming the product $ bold "A sup {roman T} x" ~=~ bold b $ in order to determine if a calculated solution is correct. .RE .KE .KS .sp 2 .RT .ne 1i .LG .B "\n(sc.\n+(ss: Matrix Statistics and Documentation" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Matrix Statistics and Documentation .XE .LP .I spError() .RS .br Determines the error status of a particular matrix. While most of the \fISparse\fR routines do return an indication that an error has occurred, some do not and so \fIspError()\fP provides the only way of uncovering these errors. .RE .KE .KS .LP .I spWhereSingular() .RS .br Returns the row and column number where the matrix was detected as singular or where a zero pivot was found. .RE .KE .KS .LP .I spGetSize() .RS .br A function that returns the size of the matrix. Either the internal or external size of the matrix is returned. The internal size of the matrix is the actual size of the matrix whereas the external size is the value of the largest row or column number. These two numbers may differ if the TRANSLATE option is used. .RE .KE .KS .LP .I spElementCount() .br .I spFillinCount() .RS .br Functions that return the total number of elements in the matrix, and the number of fill-ins in the matrix. These functions are useful for gathering statistics on matrices. .RE .KE .KS .LP .I spPrint() .RS .br This routine outputs the matrix as well as some statistics to standard output in a format that is readable by people. The matrix can be printed in either a compressed or standard format. In the standard format, a numeric value is given for each structurally nonzero element, whereas in the compressed format, only the existence or nonexistence of an element is indicated. This routine is not suitable for use on large matrices. .RE .KE .KS .LP .I spFileMatrix() .br .I spFileVector() .RS .br These two routines send a copy of the matrix and its right-hand side vector to a file. This file can then be read by the test program that is included with \fISparse\fP. Only those elements of the matrix that are structurally nonzero are output, so very large matrices can be sent to a file. .RE .KE .KS .LP .I spFileStats() .RS .br This routine calculates and sends some useful statistics concerning a matrix to a file. .RE .KE .bp .nr ss 0 1 \" Reset subsection .RT .ne 1.5i .LG .B "\n+(sc: SPARSE ROUTINES" .NL .XS \n% \" Save section title for table of contents \n(sc: Routines .XE .sp This section contains a complete list of the \fISparse\fR routines that are available to the user. Each routine is described as to its function and how to use it. The routines are listed in alphabetic order. .sp 2 .Lb spClear Sets every element in the matrix to zero. The \fISparse\fR error state is cleared to spOKAY in this routine. .sp 0.3v \fBvoid\fI spClear( Matrix )\fR .XP \(bu Argument: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to matrix that is to be cleared. .RE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspClear()\fP .XE .Lb spCondition \fIspCondition()\fP computes an estimate of the condition number using a variation on the LINPACK condition number estimation algorithm. This quantity is an measure of ill-conditioning in the matrix. To avoid problems with overflow, the reciprocal of the condition number is returned. If this number is small, and if the matrix is scaled such that uncertainties in the RHS and the matrix entries are equilibrated, then the matrix is ill-conditioned. If the this number is near one, the matrix is well conditioned. This routine must only be used after a matrix has been factored by \fIspOrderAndFactor()\fR or \fIspFactor()\fR and before it is cleared by \fIspClear()\fR or \fIspInitialize()\fR. .LP Unlike the LINPACK condition number estimator, this routines returns the L infinity condition number. This is an artifact of Sparse placing ones on the diagonal of the upper triangular matrix rather than the lower. This difference should be of no importance. .sp 0.3v .nf \fIspREAL spCondition( Matrix, NormOfMatrix, Error ) .XP \(bu Returns: .br An estimate of the L infinity condition number of the matrix. .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br The matrix for which the condition number is desired. .XP \fINormOfMatrix\fP input (spREAL) .br The L-infinity norm of the unfactored matrix as computed by \fIspNorm()\fP. .XP \fIError\fP output (\fBint *\fP) .br Used to return the error code. .RE .XP \(bu Possible errors: .nf spSINGULAR spNO_MEMORY Error is not cleared in this routine. .XP \(bu Compiler options that must be set for this routine to exist: .nf CONDITION .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspCondition()\fP .XE .Lb spCreate Allocates and initializes the data structures associated with a matrix. This routine is necessarily the first routine run for any particular matrix. .sp 0.3v .nf \fBchar *\fIspCreate( Size, Complex, Error )\fR .XP \(bu Returned: .br A pointer to the matrix is returned cast into the form of a pointer to a character. This pointer is then passed and used by the other matrix routines to refer to a particular matrix. If an error occurs, the NULL pointer is returned. .XP \(bu Arguments: .RS .XP \fISize\fP input (\fBint\fP) .br Size of matrix. When the compiler option EXPANDABLE is turned on, \fISize\fP is used as a lower bound on the size of the matrix. \fISize\fP must not be negative. .XP \fIComplex\fP input (\fBint\fP) .br Type of matrix. If \fIComplex\fP is 0 then the matrix is real, otherwise the matrix will be complex. Note that if the routines are not set up to handle the type of matrix requested, then a spPANIC error will occur. .XP \fIError\fP output (\fBint *\fP) .br Returns error flag, needed because function \fIspError()\fP will not work correctly if \fIspCreate()\fP returns NULL. .RE .XP \(bu Possible errors: .nf spNO_MEMORY spPANIC .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspCreate()\fP .XE .Lb spDeleteRowAndCol This function is used to delete a row and column from the matrix. The elements removed from the matrix are never used again and are not freed until the matrix is destroyed and so the pointers to these elements remain valid. .sp 0.3v .nf \fBvoid\fI spDeleteRowAndCol( Matrix, Row, Col )\fR .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br The matrix from which the row and column are to be deleted. .XP \fIRow\fP input (\fBint\fP) .br The row to be deleted. .XP \fICol\fP input (\fBint\fP) .br The column to be deleted. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf DELETE TRANSLATE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspDeleteRowAndCol()\fP .XE .Lb spDestroy Destroys a matrix frame and reclaims the memory. .sp 0.3v .nf \fBvoid\fI spDestroy( Matrix )\fR .XP \(bu Argument: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to the matrix frame which is to be removed from memory. .RE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspDestroy()\fP .XE .Lb spDeterminant This routine in capable of calculating the determinant of the matrix once the LU factorization has been performed. Hence, only use this routine after \fIspFactor()\fP or \fIspOrderAndFactor()\fP and before \fIspClear()\fP or \fIspInitialize()\fR. Note that the determinants of matrices can be very large or very small. On large matrices, the determinant can be far larger or smaller than can be represented by a floating point number. For this reason the mantissa and exponent of the determinant are returned separately. .sp 0.3v .nf \fBvoid\fI spDeterminant( Matrix, Exponent, Determinant )\fR .br \fBvoid\fI spDeterminant( Matrix, Exponent, Determinant, iDeterminant )\fR .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br The matrix for which the determinant is desired. .XP \fIExponent\fP output (\fBint *\fP) .br The logarithm base 10 of the scale factor for the determinant. To find the actual determinant, Exponent should be added to the exponent of \fIDeterminant\fP and \fIiDeterminant\fP. .XP \fIDeterminant\fP output (spREAL \fB*\fR) .br The real portion of the determinant. If the matrix is real, then the magnitude of this number is scaled to be greater than or equal to 1.0 and less than 10.0. Otherwise the magnitude of the complex determinant will be scaled such. .XP \fIiDeterminant\fP output (spREAL \fB*\fR) .br The imaginary portion of the determinant. When the matrix is real this pointer need not be supplied; nothing will be returned. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf DETERMINANT .XP \(bu Bugs: .br The sign of determinant may be in error if rows and columns have been added or deleted from matrix. .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspDeterminant()\fP .XE .Lb spElementCount Returns the total number of structurally nonzero elements in the matrix. .sp 0.3v .nf \fBint\fI spElementCount( Matrix )\fR .XP \(bu Returns: .br The total number of structurally nonzero elements. .XP \(bu Argument: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to the matrix. .RE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspElementCount()\fP .XE .Lb spError This function returns the error status of a matrix. .sp 0.3v .nf \fBint\fI MatrixError( Matrix )\fR .XP \(bu Returned: .br The error status of the given matrix. .XP \(bu Argument: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br The matrix for which the error status is desired. .RE .XP \(bu Possible errors: .nf spOKAY spILL_CONDITIONED spZERO_PIVOT spSINGULAR spNO_MEMORY spPANIC Error is not cleared in this routine. .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspError()\fP .XE .Lb spFactor This routine factors the matrix into LU form and is the companion routine to \fIspOrderAndFactor()\fP. Unlike \fIspOrderAndFactor()\fP, \fIspFactor()\fP cannot change the ordering. Its utility is that it is considerably faster. The standard way to use these two routines is to first use \fIspOrderAndFactor()\fP for the initial factorization. For subsequent factorizations, \fIspFactor()\fP is used. If \fIspFactor()\fP is called for the initial factorization of the matrix, then it will automatically call \fIspOrderAndFactor()\fP with the default thresholds. If \fIspFactor()\fP finds a zero on the diagonal, it will terminate early and complain. This does not necessarily mean that matrix is singular. Before a matrix is condemned as being singular, it should be run through \fIspOrderAndFactor()\fP, which can reorder the matrix and remove the offensive zero from the diagonal. .sp 0.3v .nf \fBint\fI spFactor( Matrix )\fR .XP \(bu Returned: .br The error code is returned. Possible errors are listed below. .XP \(bu Argument: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to matrix to be factored. .RE .XP \(bu Possible errors: .nf spZERO_PIVOT spNO_MEMORY spSINGULAR spILL_CONDITIONED .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspFactor()\fP .XE .Lb spFileMatrix Writes matrix to file in format suitable to be read back in by the matrix test program. Normally, \fIspFileMatrix()\fP should be executed before the matrix is factored, otherwise matrix is output in factored form. If the matrix is sent to a file without the header or data, it will be in a form that is easily plotted by typical plotting programs. .sp 0.3v .nf \fBint\fI spFileMatrix( Matrix, File, Label, Reordered, Data, Header )\fR .XP \(bu Returns: .br One is returned if routine was successful, otherwise zero is returned. The calling function can query \fIerrno\fR (the system global error variable) as to the reason why this routine failed. .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to matrix that is to be sent to file. .XP \fIFile\fP input (\fBchar *\fP) .br Name of output file. .XP \fILabel\fP input (\fBchar *\fP) .br String that is transferred to file and used as a label. String should fit on one line and have no embedded line feeds. .XP \fIReordered\fP input (\fBint\fP) .br Specifies whether the matrix should be output using the original order or in reordered form. Zero specifies original order. .XP \fIData\fP input (\fBint\fP) .br Indicates that the element values should be output along with the indices for each element. Element values are not output if \fIData\fP is zero. This parameter must be nonzero if matrix is to be read by the \fISparse\fR test program. .XP \fIHeader\fP input (\fBint\fP) .br If nonzero a header is output that includes that size of the matrix and the label. This parameter must be nonzero if matrix is to be read by the \fISparse\fP test program. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf DOCUMENTATION .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspFileMatrix()\fP .XE .Lb spFileStats Appends useful information concerning the matrix to the end of a file. If file does not exist, it is created. This file should not be the same as one used to hold the matrix or vector if the matrix is to be read by the \fISparse\fP test program. Should be executed after the matrix is factored. .sp 0.3v .nf \fBint\fI spFileStats( Matrix, File, Label )\fR .XP \(bu Returns: .br One is returned if routine was successful, otherwise zero is returned. The calling function can query \fIerrno\fR (the system global error variable) as to the reason why this routine failed. .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to matrix for which statistics are desired. .XP \fIFile\fP input (\fBchar *\fP) .br Name of output file. .XP \fILabel\fP input (\fBchar *\fP) .br String that is transferred to file and is used as a label. String should fit on one line and have no embedded line feeds. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf DOCUMENTATION .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspFileStats()\fP .XE .Lb spFileVector Appends the \fIRHS\fP vector to the end of a file in a format suitable to be read back in by the matrix test program. If file does not exist, it is created. To be compatible with the test program, if \fIspFileVector()\fP is run, it must be run after \fIspFileMatrix()\fP and use the same file. .sp 0.3v .nf \fBint\fI spFileVector( Matrix, File, RHS )\fR .br \fBint\fI spFileVector( Matrix, File, RHS, iRHS )\fR .XP \(bu Returns: .br One is returned if routine was successful, otherwise zero is returned. The calling function can query \fIerrno\fR (the system global error variable) as to the reason why this routine failed. .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to matrix that corresponds to the vector to be output. .XP \fIFile\fP input (\fBchar *\fP) .br Name of file where output is to be written. .XP \fIRHS\fP input (spREAL[]) .br The right-hand side vector. \fIRHS\fP contains only the real portion of the right-hand side vector if the matrix is complex and spSEPARATED_COMPLEX_VECTORS is set true. .XP \fIiRHS\fP input (spREAL[]) .br Right-hand side vector, imaginary portion. Not necessary if matrix is real or if spSEPARATED_COMPLEX_VECTORS is set false. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf DOCUMENTATION .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspFileVector()\fP .XE .Lb spFillinCount Returns the total number of fill-ins in the matrix. A fill-in is an element that is originally structurally zero, but becomes nonzero during the factorization. .sp 0.3v .nf \fBint\fI spFillinCount( Matrix )\fR .XP \(bu Returns: .br The total number of fill-ins. .XP \(bu Argument: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to the matrix. .RE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspFillinCount()\fP .XE .Lb spGetAdmittance Performs same function as \fIspGetElement()\fP except rather than one element, all four matrix elements for a floating admittance are reserved. This routine also works if the admittance is grounded (zero is the ground node). This function returns a group of pointers to the four elements through \fITemplate\fP, which is an output. They are used by the \fIspADD_QUAD()\fP macros to directly access matrix elements during subsequent loads of the matrix. \fIspGetAdmittance()\fR arranges the pointers in \fITemplate\fR so that the \fIspADD_QUAD()\fR routines add the admittance to the elements at [\fINode1,Node1\fP] and [\fINode2,Node2\fP] and subtract the admittance from the elements at [\fINode1,Node2\fP] and [\fINode2,Node1\fP]. This routine is only to be used before \fIspMNA_Preorder()\fP, \fIspFactor()\fP or \fIspOrderAndFactor()\fP unless the compiler flag TRANSLATE is enabled. .sp 0.3v .nf \fBint\fI spGetAdmittance( Matrix, Node1, Node2, Template )\fR .XP \(bu Returned: .br The error code is returned. Possible errors are listed below. \fIspGetAdmittance()\fR does not clear the error state, so it is possible to ignore the return code of each \fIspGetAdmittance()\fR call, and check for errors after constructing the whole matrix by calling \fIspError()\fR. .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to the matrix that admittance is to be installed. .XP \fINode1\fP input (\fBint\fP) .br One node number for the admittance. \fINode1\fP must be in the range [0..\fISize\fP] unless either the TRANSLATE or EXPANDABLE compiler flags are set true. In either case \fINode1\fP must not be negative. .XP \fINode2\fP input (\fBint\fP) .br Other node number for the admittance. \fINode2\fP must be in the range [0..\fISize\fP] unless either the TRANSLATE or EXPANDABLE compiler flags are set true. In either case \fINode2\fP must not be negative. .XP \fITemplate\fP output (\fBstruct \fIspTemplate\fB *\fR) .br Collection of pointers to four elements that are later used to directly address elements. User must supply the template, this routine will fill it. .RE .XP \(bu Possible errors: .nf spNO_MEMORY Error is not cleared in this routine. .XP \(bu Compiler options that must be set for this routine to exist: .nf QUAD_ELEMENT .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspGetAdmittance()\fP .XE .Lb spGetElement Reserves an element at [\fIRow,Col\fP] and returns a pointer to it. If element is not found then it is created and spliced into matrix. A pointer to the real portion of the element is returned. This pointer is later used by the \fIspADD_ELEMENT()\fR macros to directly access the element. This routine is only to be used before \fIspMNA_Preorder()\fP, \fIspFactor()\fP or \fIspOrderAndFactor()\fP unless the compiler option TRANSLATE is set true. .sp 0.3v .nf spREAL \fB*\fIspGetElement( Matrix, Row, Col )\fR .XP \(bu Returned: .br Returns a pointer to the element. This pointer is then used to directly access the element during successive builds. Returns NULL if insufficient memory is available. \fIspGetElement()\fR does not clear the error state, so it is possible to ignore the return code of each \fIspGetElement()\fR call, and check for errors after constructing the whole matrix by calling \fIspError()\fR. .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to the matrix that the element is to be added to. .XP \fIRow\fP input (\fBint\fP) .br Row index for element. \fIRow\fP must be in the range [0..\fISize\fR] unless either the TRANSLATE or EXPANDABLE compiler flags are set true. In either case \fIRow\fP must not be negative though it may be zero. If zero then the element is not entered into the matrix, but is otherwise treated normally. .XP \fICol\fP input (\fBint\fP) .br Column index for element. \fICol\fP must be in the range [0..\fISize\fR] unless either the TRANSLATE or EXPANDABLE compiler flags are set true. In either case \fICol\fP must not be negative though it may be zero. If zero then the element is not entered into the matrix, but is otherwise treated normally. .RE .XP \(bu Possible errors: .nf spNO_MEMORY Error is not cleared in this routine. .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspGetElement()\fP .XE .Lb spGetInitInfo With the INITIALIZE compiler option enabled \fISparse\fP allows the user to keep initialization information with each structurally nonzero matrix element. Each element has a pointer (referred to as \fIpInitInfo\fR) that is set and used by the user. This routine returns \fIpInitInfo\fR from a particular matrix element. .sp 0.3v .nf \fBchar *\fIspGetInitInfo( pElement )\fR .XP \(bu Returned: .br The user installed pointer \fIpInitInfo\fR. .XP \(bu Argument: .RS .XP \fIpElement\fR input (spREAL \fB*\fR) .br Pointer to the element to which \fIpInitInfo\fR is attached. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf INITIALIZE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspGetInitInfo()\fP .XE .Lb spGetOnes Performs a similar function to \fIspGetAdmittance()\fP except that the four reserved matrix elements are assumed to be structural ones generated by components without admittance representations during a modified nodal analysis. Positive ones are placed at [\fIPos,Eqn\fP] and [\fIEqn,Pos\fP] and negative ones are placed at [\fINeg,Eqn\fP] and [\fIEqn,Neg\fP]. This function returns a group of pointers to the four elements through \fITemplate\fP, which is an output. They are used by the \fIspADD_QUAD()\fP macros to add the ones directly to the matrix elements during subsequent loads of the matrix. This routine is only to be used before \fIspMNA_Preorder()\fP, \fIspFactor()\fP or \fIspOrderAndFactor()\fP unless the compiler flag TRANSLATE is set true. .sp 0.3v .nf \fBint\fI spGetOnes( Matrix, Pos, Neg, Eqn, Template )\fR .XP \(bu Returned: .br The error code is returned. Possible errors are listed below. \fIspGetOnes()\fR does not clear the error state, so it is possible to ignore the return code of each \fIspGetOnes()\fR call, and check for errors after constructing the whole matrix by calling \fIspError()\fR. .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to the matrix that ones are to be entered in. .XP \fIPos\fP input (\fBint\fP) .br Number of positive node. Must be in the range of [0..\fISize\fR] unless either the options EXPANDABLE or TRANSLATE are used. Zero is the ground row. In no case may \fIPos\fP be less than zero. .XP \fINeg\fP input (\fBint\fP) .br Number of negative node. Must be in the range of [0..\fISize\fP] unless either the options EXPANDABLE or TRANSLATE are used. Zero is the ground row. In no case may \fINeg\fP be less than zero. .XP \fIEqn\fP input (\fBint\fP) .br Row that contains the branch equation. Must be in the range of [1..\fISize\fP] unless either the options EXPANDABLE or TRANSLATE are used. In no case may \fIEqn\fP be less than one. .XP \fITemplate\fP output (\fBstruct \fIspTemplate\fB *\fR) .br Collection of pointers to four elements that are later used to directly address elements. User must supply the template, this routine will fill it. .RE .XP \(bu Possible errors: .nf spNO_MEMORY Error is not cleared in this routine. .XP \(bu Compiler options that must be set for this routine to exist: .nf QUAD_ELEMENT .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspGetOnes()\fP .XE .Lb spGetQuad Similar to \fIspGetAdmittance()\fP, except that \fIspGetAdmittance()\fP only handles 2-terminal components, whereas \fIspGetQuad()\fP handles simple 4-terminals as well. These 4-terminals are simply generalized 2-terminals with the option of having the sense terminals different from the source and sink terminals. \fIspGetQuad()\fP installs four elements into the matrix and returns their pointers in the \fITemplate\fR structure, which is an output. The pointers are arranged in \fITemplate\fR such that when passed to one of the \fIspADD_QUAD()\fR macros along with an admittance, the admittance will be added to the elements at [\fIRow1,Col1\fP] and [\fIRow2,Col2\fP] and subtracted from the elements at [\fIRow1,Col2\fP] and [\fIRow2,Col1\fP]. The routine works fine if any of the rows and columns are zero. This routine is only to be used before \fIspMNA_Preorder()\fP, \fIspFactor()\fP or \fIspOrderAndFactor()\fP unless TRANSLATE is set true. .sp 0.3v .nf \fBint\fI spGetQuad( Matrix, Row1, Row2, Col1, Col2, Template )\fR .XP \(bu Returned: .br The error code is returned. Possible errors are listed below. \fIspGetQuad()\fR does not clear the error state, so it is possible to ignore the return code of each \fIspGetQuad()\fR call, and check for errors after constructing the whole matrix by calling \fIspError()\fR. .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to the matrix that quad is to be entered in. .XP \fIRow1\fP input (\fBint\fP) .br First row index for the elements. \fIRow1\fP must be in the range [0..\fISize\fP] unless either the TRANSLATE or EXPANDABLE compiler flags are set true. In either case \fIRow1\fP must not be negative. .XP \fIRow2\fP input (\fBint\fP) .br Second row index for the elements. \fIRow2\fP must be in the range [0..\fISize\fP] unless either the TRANSLATE or EXPANDABLE compiler flags are set true. In either case \fIRow2\fP must not be negative. .XP \fICol1\fP input (\fBint\fP) .br First column index for the elements. \fICol1\fP must be in the range [0..\fISize\fP] unless either the TRANSLATE or EXPANDABLE compiler flags are set true. In either case \fICol1\fP must not be negative. .XP \fICol2\fP input (\fBint\fP) .br Second column index for the elements. \fICol2\fP must be in the range [0..\fISize\fP] unless either the TRANSLATE or EXPANDABLE compiler flags are set true. In either case \fICol2\fP must not be negative. .XP \fITemplate\fP output (\fBstruct \fIspTemplate\fB *\fR) .br Collection of pointers to four elements that are later used to directly address elements. User must supply the template, this routine will fill it. .RE .XP \(bu Possible errors: .nf spNO_MEMORY Error is not cleared in this routine. .XP \(bu Compiler options that must be set for this routine to exist: .nf QUAD_ELEMENT .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspGetQuad()\fP .XE .Lb spGetSize Returns the size of the matrix, either the internal or external size of the matrix is returned. The internal size is the actual number of rows and columns in the matrix. The external size is equal to the largest row or column number. These numbers will be the same unless the TRANSLATE option is enabled. .sp 0.3v .nf \fBint\fI spGetSize( Matrix, External )\fR .XP \(bu Returned: .br The size of the matrix. .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to the matrix for which the size is desired. .XP \fIExternal\fP input (\fBint\fP) .br If \fIExternal\fR is nonzero, the external size of the matrix is returned, otherwise the internal size of the matrix is returned. .RE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspGetSize()\fP .XE .Lb spInitialize \fIspInitialize()\fR is a user customizable way to initialize the matrix. Passed to this routine is a function pointer. \fIspInitialize()\fR sweeps through every element in the matrix and checks the \fIpInitInfo\fR pointer (the user supplied pointer). If the \fIpInitInfo\fR is NULL, which is true unless the user changes it (always true for fill-ins), then the element is zeroed. Otherwise, the function pointer is called and passed the \fIpInitInfo\fR pointer as well as the element pointer and the external row and column numbers allowing the user to set the value of each element and perhaps the right-hand side vector. .LP The user function (\fIpInit()\fR) is expected to return a nonzero integer if there is a fatal error and zero otherwise. Upon encountering a nonzero return code, \fIspInitialize()\fR terminates and returns the error code. .LP The \fISparse\fR error state is cleared to spOKAY in this routine. .sp 0.3v .nf \fBint\fI spInitialize( Matrix, pInit )\fR .XP \(bu Returns: .br The error code returned by \fIpInit\fR. .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to the matrix that is to be initialized. .XP \fIpInit\fP input (\fB(*int)()\fP) .br Pointer to a function that, given a pointer to an element, a pointer to the users data structure containing initialization information for that element, and the row and column number of the element, initializes it. .RE .LP \fBint\fI pInit( pElement, pInitInfo, Row, Col )\fR .XP \(bu Returns: .br Nonzero if fatal error, zero otherwise. .XP \(bu Arguments: .RS .XP \fIpElement\fP input (spREAL \fB*\fP) .br The pointer to the real portion of the element. The real portion can be accessed using either \fI*pElement\fR or \fIpElement[0]\fR. The imaginary portion can be accessed using either \fI*(pElement+1)\fR or \fIpElement[1]\fR. .XP \fIpInitInfo\fP input (\fBchar *\fP) .br The user-installed pointer to the initialization data structure. .XP \fIRow\fP input (\fBint\fP) .br The external row number of the element. .XP \fICol\fP input (\fBint\fP) .br The external column number of the element. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf INITIALIZE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspInitialize()\fP .XE .Lb spInstallInitInfo With the INITIALIZE compiler option enabled \fISparse\fP allows the user to keep initialization information with each structurally nonzero matrix element. Each element has a pointer (referred to as \fIpInitInfo\fR) that is set and used by the user. This routine installs the pointer \fIpInitInfo\fR into a particular matrix element. .sp 0.3v .nf \fBvoid\fI spInstallInitInfo( pElement, pInitInfo )\fR .XP \(bu Arguments: .RS .XP \fIpElement\fR input (spREAL \fB*\fR) .br Pointer to the element to which \fIpInitInfo\fR is to be attached. .XP \fIpInitInfo\fR input (\fBchar *\fR) .br The pointer \fIpInitInfo\fR. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf INITIALIZE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspInstallInitInfo()\fP .XE .Lb spLargestElement If this routine is called before the matrix is factored, it returns the absolute value of the largest element in the matrix. If called after the matrix has been factored, it returns a lower bound on the absolute value of the largest element that occurred in any of the reduced submatrices during the factorization. The ratio of these two numbers (factored/unfactored) is the growth, which can be used to determine if the pivoting order is adequate. A large growth implies that considerable error has been made in the factorization and that it is probably a good idea to reorder the matrix. If a large growth in encountered after using \fIspFactor()\fR, reconstruct the matrix and refactor using \fIspOrderAndFactor()\fR. If a large growth is encountered after using \fIspOrderAndFactor()\fR, refactor using \fIspOrderAndFactor()\fR with the pivot threshold increased, say to 0.1. .sp 0.3v .nf spREAL\fI spLargestElement( Matrix )\fR .XP \(bu Returns: .br If matrix is unfactored, returns the magnitude of the largest element in the matrix. If the matrix is factored, a bound on the magnitude of the largest element in any of the reduced submatrices is returned. .XP \(bu Argument: .RS .XP \fIMatrix\fR input (\fBchar *\fR) .br Pointer to the matrix. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf STABILITY .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspLargestElement()\fP .XE .Lb spMNA_Preorder This routine massages modified node admittance matrices to improve the performance of \fIspOrderAndFactor()\fP. It tries to remove structural zeros from the diagonal by exploiting the fact that the row and column associated with a zero diagonal usually have structural ones placed symmetrically. For this routine to work, the structural ones must be exactly equal to either one or negative one. This routine should be used only on modified node admittance matrices and must be executed after the matrix has been built but before \fIspScale()\fP, \fIspNorm()\fP, \fIspMultiply()\fP, \fIspFactor()\fP, \fIspOrderAndFactor()\fP or \fIspDeleteRowAndCol()\fP are executed. It should be executed for the initial factorization only. .sp 0.3v .nf \fBvoid\fI spMNA_Preorder( Matrix )\fR .XP \(bu Argument: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .IP Pointer to the matrix to be preordered. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf MODIFIED_NODAL .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspMNA_Preorder()\fP .XE .Lb spMultiply Multiplies \fIMatrix\fP by \fISolution\fP on the right to find \fIRHS\fP. Assumes matrix has not been factored. This routine can be used as a test to see if solutions are correct. .sp 0.3v \fBvoid\fI spMultiply( Matrix, RHS, Solution )\fR .br \fBvoid\fI spMultiply( Matrix, RHS, Solution, iRHS, iSolution )\fR .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to the matrix. .XP \fIRHS\fP output (spREAL[]) .br \fIRHS\fP is the right hand side vector. This is what is being solved for. \fIRHS\fP contains only the real portion of the right-hand side if spSEPARATED_COMPLEX_VECTORS is set true. .XP \fISolution\fP input (spREAL[]) .br \fISolution\fP is the vector being multiplied by the matrix. \fISolution\fP contains only the real portion of that vector if spSEPARATED_COMPLEX_VECTORS is set true. .XP \fIiRHS\fP output (spREAL[]) .br \fIiRHS\fP is the imaginary portion of the right hand side. This is what is being solved for. It is only necessary to supply \fIiRHS\fP if the matrix is complex and spSEPARATED_COMPLEX_VECTORS is set true. .XP \fIiSolution\fP input (spREAL[]) .br \fIiSolution\fP is the imaginary portion of the vector being multiplied by the matrix. It is only necessary to supply \fIiRHS\fP if the matrix is complex and spSEPARATED_COMPLEX_VECTORS is set true. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf MULTIPLICATION .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspMultiply()\fP .XE .Lb spMultTransposed Multiplies transposed \fIMatrix\fP by \fISolution\fP on the right to find \fIRHS\fP. Assumes matrix has not been factored. This routine can be used as a test to see if solutions are correct. .sp 0.3v \fBvoid\fI spMultTransposed( Matrix, RHS, Solution )\fR .br \fBvoid\fI spMultTransposed( Matrix, RHS, Solution, iRHS, iSolution )\fR .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to the matrix. .XP \fIRHS\fP output (spREAL[]) .br \fIRHS\fP is the right hand side vector. This is what is being solved for. \fIRHS\fP contains only the real portion of the right-hand side if spSEPARATED_COMPLEX_VECTORS is set true. .XP \fISolution\fP input (spREAL[]) .br \fISolution\fP is the vector being multiplied by the matrix. \fISolution\fP contains only the real portion of that vector if spSEPARATED_COMPLEX_VECTORS is set true. .XP \fIiRHS\fP output (spREAL[]) .br \fIiRHS\fP is the imaginary portion of the right hand side. This is what is being solved for. It is only necessary to supply \fIiRHS\fP if the matrix is complex and spSEPARATED_COMPLEX_VECTORS is set true. .XP \fIiSolution\fP input (spREAL[]) .br \fIiSolution\fP is the imaginary portion of the vector being multiplied by the matrix. It is only necessary to supply \fIiRHS\fP if the matrix is complex and spSEPARATED_COMPLEX_VECTORS is set true. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf MULTIPLICATION TRANSPOSE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspMultTransposed()\fP .XE .Lb spNorm Computes and returns the L-infinity norm of an unfactored matrix. This number is used in computing the condition number of the matrix. It is a fatal error to pass this routine a factored matrix. .sp 0.3v spREAL\fI spNorm( Matrix )\fR .XP \(bu Returns: .br The largest absolute row sum (the L-infinity norm) of the matrix. .XP \(bu Argument: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to the matrix. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf CONDITION .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspNorm()\fP .XE .Lb spOrderAndFactor This routine chooses a pivot order for the matrix and factors it into LU form. It handles both the initial factorization and subsequent factorizations when a reordering or threshold pivoting is desired. This is handled in a manner that is transparent to the user. .sp 0.3v \fBint\fI spOrderAndFactor( Matrix, RHS, Threshold, AbsoluteThreshold, DiagPivoting )\fR .KE .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspOrderAndFactor()\fP .XE .XP \(bu Returned: .br The error code is returned. Possible errors are listed below. .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to matrix to be factored. .XP \fIRHS\fP input (spREAL[]) .br Representative \fIRHS\fP vector that is used to determine pivoting order when the right-hand side vector is sparse. If a term in \fIRHS\fP is zero, it is assumed that it will usually be zero. Conversely, a nonzero term in \fIRHS\fP indicates that the term will often be nonzero. If \fIRHS\fP is a NULL pointer then the right-hand side vector is assumed to be full and it is not used when determining the pivoting order. .XP \fIThreshold\fR input (spREAL) .br This is the pivot threshold, which should be between zero and one. If it is one then the pivoting method becomes complete pivoting, which is very slow and tends to fill up the matrix. If it is set close to zero the pivoting method becomes strict Markowitz with no threshold. The pivot threshold is used to eliminate pivot candidates that would cause excessive element growth if they were used. Element growth is the cause of roundoff error, which can occur even in well-conditioned matrices. Setting the threshold large will reduce element growth and roundoff error, but setting it too large will cause execution time to be excessive and will result in a large number of fill-ins. If this occurs, accuracy can actually be degraded because of the large number of operations required on the matrix due to the large number of fill-ins. A good value for diagonal pivoting seems to be 0.001 while a good value for complete pivoting appears to be 0.1. The default is chosen by giving a value larger than one or less than or equal to zero. Once the pivot threshold is set, the value becomes the new default for later calls to \fIspOrderAndFactor\fR. The threshold value should be increased and the matrix re-solved if growth is found to be excessive. Changing the pivot threshold does not improve performance on matrices where growth is low, as is often the case with ill-conditioned matrices. The default value of \fIThreshold\fR was choosen for use with nearly diagonally dominant matrices such as node- and modified-node admittance matrices. For these matrices it is usually best to use diagonal pivoting. For matrices without a strong diagonal, it is usually best to use a larger threshold, such as 0.01 or 0.1. .XP \fIAbsoluteThreshold\fP input (spREAL) .br The absolute magnitude an element must have to be considered as a pivot candidate, except as a last resort. This number should be set significantly smaller than the smallest diagonal element that is is expected to be placed in the matrix. If there is no reasonable prediction for the lower bound on these elements, then \fIAbsoluteThreshold\fP should be set to zero. \fIAbsoluteThreshold\fP is used to reduce the possibility of choosing as a pivot an element that has suffered heavy cancellation and as a result mainly consists of roundoff error. Note that if \fIAbsoluteThreshold\fP is set too large, it could drastically increase the time required to factor and solve the matrix. \fIAbsoluteThreshold\fP should be nonnegative. If no element in the matrix is larger than \fIAbsoluteThreshold\fR, the warning spILL_CONDITIONED is returned. .XP \fIDiagPivoting\fP input (int) .br A flag indicating that pivot selection should be confined to the diagonal if possible. If \fIDiagPivoting\fR is nonzero and if DIAGONAL_PIVOTING is enabled pivots will be chosen only from the diagonal unless there are no diagonal elements that satisfy the threshold criteria. Otherwise, the entire reduced submatrix is searched when looking for a pivot. The diagonal pivoting in \fISparse\fR is efficient and well refined, while the complete pivoting is not. For symmetric and near symmetric matrices, it is best to use diagonal pivoting because it results in the best performance when reordering the matrix and when factoring the matrix without ordering. If there is a considerable amount of nonsymmetry in the matrix, then complete pivoting may result in a better equation ordering simply because there are more pivot candidates to choose from. A better ordering results in faster subsequent factorizations. However, the initial pivot selection process takes considerably longer for complete pivoting. .RE .KS .XP \(bu Possible errors: .nf spNO_MEMORY spSINGULAR spILL_CONDITIONED .Le .RE .Lb spPartition This routine determines the cost to factor each row using both direct and indirect addressing and decides, on a row-by-row basis, which addressing mode is fastest. This information is used in \fIspFactor()\fR to speed the factorization. .LP When factoring a previously ordered matrix using \fIspFactor()\fR, f\ISparse\fR operates on a row-at-a-time basis. For speed, on each step, the row being updated is copied into a full vector and the operations are performed on that vector. This can be done one of two ways, either using direct addressing or indirect addressing. Direct addressing is fastest when the matrix is relatively dense and indirect addressing is best when the matrix is quite sparse. The user selects the type of partition used with \fIMode\fR. If \fIMode\fR is set to spDIRECT_PARTITION, then the all rows are placed in the direct addressing partition. Similarly, if \fIMode\fR is set to spINDIRECT_PARTITION, then the all rows are placed in the indirect addressing partition. By setting \fIMode\fR to spAUTO_PARTITION, the user allows \fISparse\fR to select the partition for each row individually. \fIspFactor()\fR generally runs faster if \fISparse\fR is allowed to choose its own partitioning, however choosing a partition is expensive. The time required to choose a partition is of the same order of the cost to factor the matrix. If you plan to factor a large number of matrices with the same structure, it is best to let \fISparse\fR choose the partition. Otherwise, you should choose the partition based on the predicted density of the matrix. By default (i.e., if \fIspPartition()\fR is never called), \fISparse\fR chooses the partition for each row individually. .sp 0.3v \fBvoid\fI spPartition( Matrix, Mode )\fR .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to matrix to be partitioned. .XP \fIMode\fP input (\fBint\fR) .br Mode must be one of three special codes: spDIRECT_PARTITION, spINDIRECT_PARTITION, or spAUTO_PARTITION. .RE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspPartition()\fP .XE .Lb spPrint Formats and send the matrix to standard output. Some elementary statistics are also output. The matrix is output in a format that is readable by people. This routine should not be used on large matrices. .sp 0.3v \fBvoid\fI spPrint( Matrix, PrintReordered, Data, Header )\fR .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to matrix to be printed. .XP \fIPrintReordered\fP input (\fBint\fP) .br Indicates whether the matrix should be printed out in its original form, as input by the user, or whether it should be printed in its reordered form, as used internally by the matrix routines. A zero indicates that the matrix should be printed as inputed, a one indicates that it should be printed reordered. .XP \fIData\fP input (\fBint\fP) .br Boolean flag that when false indicates that output should be compressed such that only the existence of an element should be indicated rather than giving the actual value. Thus 10 times as many elements can be printed on a row. A zero indicates that the matrix should be printed compressed. A one signifies that the matrix should be printed in all its glory. .XP \fIHeader\fP input (\fBint\fP) .br A flag indicating that extra information should be printed, such as row and column numbers. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf DOCUMENTATION .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspPrint()\fP .XE .Lb spPseudoCondition Computes the magnitude of the ratio of the largest to the smallest pivots. This quantity is an indicator of ill-conditioning in the matrix. If this ratio is large, and if the matrix is scaled such that uncertainties in the right-hand side vector and the matrix entries are equilibrated, then the matrix is ill-conditioned. However, a small ratio does not necessarily imply that the matrix is well-conditioned. This routine must only be used after a matrix has been factored by \fIspOrderAndFactor()\fR or \fIspFactor()\fR and before it is cleared by \fIspClear()\fR or \fIspInitialize()\fR. The pseudocondition is faster to compute than the condition number calculated by \fIspCondition()\fR, but is not as informative. .sp 0.3v spREAL \fI spPseudoCondition( Matrix )\fR .XP \(bu Returns: .br The magnitude of the ratio of the largest to smallest pivot used during previous factorization. If the matrix was singular, zero is returned. .XP \(bu Argument: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to matrix. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf PSEUDOCONDITION .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspPseudoCondition()\fP .XE .Lb spRoundoff Returns a bound on the magnitude of the largest element in $bold E ~=~ bold A - bold LU$, where $bold E$ represents error in the matrix resulting from roundoff during the factorization. .sp 0.3v spREAL \fI spRoundoff( Matrix, Rho )\fR .XP \(bu Returns: .br Returns a bound on the magnitude of the largest element in $bold E ~=~ bold A - bold LU$. .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to matrix. Matrix must be factored. .XP \fIRho\fP input (spREAL) .br The bound on the magnitude of the largest element in any of the reduced submatrices. This is the number computed by the function \fIspLargestElement()\fR when given a factored matrix. If this number is negative, the bound will be computed automatically. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf STABILITY .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspRoundoff()\fP .XE .Lb spScale This function scales the matrix to enhance the possibility of finding a good pivoting order. Note that scaling enhances accuracy of the solution only if it affects the pivoting order, so it only makes sense to scale the matrix before \fIspOrderAndFactor()\fP. There are several things to take into account when choosing the scale factors. First, the scale factors are directly multiplied times the elements in the matrix. To prevent roundoff, each scale factor should be equal to an integer power of the number base of the machine. Since most machines operate in base two, scale factors should be a power of two. Second, the matrix should be scaled such that the matrix of element uncertainties is equilibrated. Third, this function multiplies the scale factors times the elements, so if one row tends to have uncertainties 1000 times smaller than the other rows, then its scale factor should be 1024, not 1/1024. Fourth, to save time, this function does not scale rows or columns if their scale factors are equal to one. Thus, the scale factors should be normalized to the most common scale factor. Rows and columns should be normalized separately. For example, if the size of the matrix is 100 and 10 rows tend to have uncertainties near 1e-6 and the remaining 90 have uncertainties near 1e-12, then the scale factor for the 10 should be 1/1,048,576 and the scale factors for the remaining 90 should be 1. Fifth, since this routine directly operates on the matrix, it is necessary to apply the scale factors to the \fIRHS\fP and \fISolution\fP vectors. It may be easier to simply use \fIspOrderAndFactor()\fP on a scaled matrix to choose the pivoting order, and then throw away the matrix. Subsequent factorizations, performed with \fIspFactor()\fP, will not need to have the \fIRHS\fP and \fISolution\fP vectors descaled. .sp 0.3v \fBvoid\fI spScale( Matrix, RHS_ScaleFactors, SolutionScaleFactors )\fR .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to the matrix to be scaled. .XP \fIRHS_ScaleFactors\fP input (spREAL[]) .br The array of RHS scale factors. These factors scale the rows. All scale factors are real-valued. .XP \fISolutionScaleFactors\fP input (spREAL[]) .br The array of Solution scale factors. These factors scale the columns. All scale factors are real-valued. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf SCALING .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspScale()\fP .XE .Lb spSetComplex The type of the matrix may then be toggled back and forth between complex and real. This function changes the type of matrix to complex. For the matrix to be set complex, the compiler option spCOMPLEX must be set true. .sp 0.3v \fBvoid\fI spSetComplex( Matrix )\fR .XP \(bu Argument: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .IP The matrix that is to be to be complex. .RE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspSetComplex()\fP .XE .Lb spSetReal The type of the matrix may then be toggled back and forth between complex and real. This function changes the type of matrix to real. For the matrix to be set real, the compiler option REAL must be set true. .sp 0.3v \fBvoid\fI spSetReal( Matrix )\fR .XP \(bu Argument: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br The matrix that is to be real. .RE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspSetReal()\fP .XE .Lb spSolve Performs the forward and backward elimination to find the unknown \fISolution\fP vector from \fIRHS\fP and the factored matrix. .sp 0.3v \fBvoid\fI spSolve( Matrix, RHS, Solution )\fR .br \fBvoid\fI spSolve( Matrix, RHS, Solution, iRHS, iSolution )\fR .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to matrix. .XP \fIRHS\fP input (spREAL[]) .br \fIRHS\fP is the input data array, the right-hand side vector. \fIRHS\fP contains only the real portion of the right-hand side vector if spSEPARATED_COMPLEX_VECTORS is set true. \fIRHS\fP is undisturbed and may be reused for other solves. .XP \fISolution\fP output (spREAL[]) .br \fISolution\fP is the output data array, the unknown vector. This routine is constructed such that \fIRHS\fP and \fISolution\fP can be the same array. \fISolution\fP contains only the real portion of the unknown vector if spSEPARATED_COMPLEX_VECTORS is set true. .XP \fIiRHS\fP input (spREAL[]) .br \fIiRHS\fP is the imaginary portion of the input data array, the right-hand side vector. This data is undisturbed and may be reused for other solves. This argument is unnecessary if the matrix is real or spSEPARATED_COMPLEX_VECTORS is set false. .XP \fIiSolution\fP output (spREAL[]) .br \fIiSolution\fP is the imaginary portion of the output data array. This routine is constructed such that \fIiRHS\fP and \fIiSolution\fP can be the same array. This argument is unnecessary if the matrix is real or spSEPARATED_COMPLEX_VECTORS is set false. .RE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspSolve()\fP .XE .Lb spSolveTransposed Performs the forward and backward elimination to find the unknown \fISolution\fP vector from \fIRHS\fP and the transposed factored matrix. This routine is useful when performing sensitivity analysis on a circuit using the adjoint method. .sp 0.3v \fBvoid\fI spSolveTransposed( Matrix, RHS, Solution )\fR .br \fBvoid\fI spSolveTransposed( Matrix, RHS, Solution, iRHS, iSolution )\fR .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to matrix. .XP \fIRHS\fP input (spREAL[]) .br \fIRHS\fP is the input data array, the right-hand side vector. \fIRHS\fP contains only the real portion of the right-hand side vector if spSEPARATED_COMPLEX_VECTORS is set true. \fIRHS\fP is undisturbed and may be reused for other solves. .XP \fISolution\fP output (spREAL[]) .br \fISolution\fP is the output data array, the unknown vector. This routine is constructed such that \fIRHS\fP and \fISolution\fP can be the same array. \fISolution\fP contains only the real portion of the unknown vector if spSEPARATED_COMPLEX_VECTORS is set true. .XP \fIiRHS\fP input (spREAL[]) .br \fIiRHS\fP is the imaginary portion of the input data array, the right-hand side vector. This data is undisturbed and may be reused for other solves. This parameter is unnecessary if the matrix is real or spSEPARATED_COMPLEX_VECTORS is set false. .XP \fIiSolution\fP output (spREAL[]) .br \fIiSolution\fP is the imaginary portion of the output data array. This routine is constructed such that \fIiRHS\fP and \fIiSolution\fP can be the same array. This parameter is unnecessary if the matrix is real or spSEPARATED_COMPLEX_VECTORS is set false. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf TRANSPOSE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspSolveTransposed()\fP .XE .Lb spStripFills \fIspStripFills()\fP strips all accumulated fill-ins from a matrix. This is often a useful thing to do before reordering a matrix to help insure that subsequent factorizations will be as efficient as possible. .sp 0.3v .nf \fBvoid\fI spStripFills( Matrix )\fR .XP \(bu Argument: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br The matrix to be stripped. .RE .XP \(bu Compiler options that must be set for this routine to exist: .nf STRIP .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspStripFills()\fP .XE .Lb spWhereSingular This function returns the row and column number where the matrix was detected as singular or where a zero pivot was found. .sp 0.3v \fBvoid\fI spWhereSingular( Matrix, Row, Col )\fR .XP \(bu Arguments: .RS .XP \fIMatrix\fP input (\fBchar *\fP) .br Pointer to matrix. .XP \fIRow\fP output (\fBint *\fP) .br The row number. .XP \fIRow\fP output (\fBint *\fP) .br The column number. .RE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspWhereSingular()\fP .XE .bp .nr ss 0 1 \" Reset subsection .RT .ne 1.5i .LG .B "\n+(sc: MACRO FUNCTIONS" .NL .XS \n% \" Save section title for table of contents \n(sc: Macro Functions .XE These macro functions are used to quickly enter data into the matrix using pointers. These pointers are originally acquired by the user from \fIspGetElement()\fP, \fIspGetAdmittance()\fP, \fIspGetQuad()\fP, and \fIspGetOnes()\fP during the initial loading of the matrix. These macros work correctly even if the elements they are to add data to are in row or column zero. .PP The macros reside in the file \fBspExports.h\fP. To use them, this file must be included in the file of the calling routine and that routine must be written in C. .Lb spADD_REAL_ELEMENT Macro function that adds a real value to an element in the matrix by a pointer. .sp 0.3v \fIspADD_REAL_ELEMENT( pElement , Real )\fR .XP \(bu Arguments: .RS .XP \fIpElement\fP input (spREAL \fB*\fP) .br A pointer to the element to which \fIReal\fR is to be added. .XP \fIReal\fP input (spREAL) .br The real value that is to be added to the element. .RE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspADD_REAL_ELEMENT()\fP .XE .Lb spADD_IMAG_ELEMENT Macro function that adds a imaginary value to an element in the matrix by a pointer. .sp 0.3v \fIspADD_IMAG_ELEMENT( pElement , Imag )\fR .XP \(bu Arguments: .RS .XP \fIpElement\fP input (spREAL \fB*\fP) .br A pointer to the element to which \fIImag\fR is to be added. .XP \fIImag\fP input (spREAL) .br The imaginary value that is to be added to the element. .RE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspADD_IMAG_ELEMENT()\fP .XE .Lb spADD_COMPLEX_ELEMENT Macro function that adds a complex value to an element in the matrix by a pointer. .sp 0.3v \fIspADD_COMPLEX_ELEMENT( pElement, Real, Imag )\fR .XP \(bu Arguments: .RS .XP \fIpElement\fP input (spREAL \fB *\fP) .br A pointer to the element to which \fIReal\fR and \fIImag\fR are to be added. .XP \fIReal\fP input (spREAL) .br The real value that is to be added to the element. .XP \fIImag\fP input (spREAL) .br The imaginary value that is to be added to the element. .RE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspADD_COMPLEX_ELEMENT()\fP .XE .Lb spADD_REAL_QUAD Macro that adds a real value to the four elements specified by \fITemplate\fP. The value is added to the first two elements in \fITemplate\fR, and subtracted from the last two. .sp 0.3v \fIspADD_REAL_QUAD( Template, Real )\fR .XP \(bu Arguments: .RS .XP \fITemplate\fP input (\fBstruct \fIspTemplate\fR) .br Data structure containing the pointers to four matrix elements. .XP \fIReal\fP input (spREAL) .br Real value to be added to the elements. .RE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspADD_REAL_QUAD()\fP .XE .Lb spADD_IMAG_QUAD Macro that adds an imaginary value to the four elements specified by \fITemplate\fP. The value is added to the first two elements in \fITemplate\fR, and subtracted from the last two. .sp 0.3v \fIspADD_IMAG_QUAD( Template, Imag )\fR .XP \(bu Arguments: .RS .XP \fITemplate\fP input (\fBstruct \fIspTemplate\fR) .br Data structure containing the pointers to four matrix elements. .XP \fIImag\fP input (spREAL) .br Imaginary value to be added to the elements. .RE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspADD_IMAG_QUAD()\fP .XE .Lb spADD_COMPLEX_QUAD Macro that adds a complex value to the four elements specified by \fITemplate\fP. The value is added to the first two elements in \fITemplate\fR, and subtracted from the last two. .sp 0.3v \fIspADD_COMPLEX_QUAD( Template, Real, Imag )\fR .XP \(bu Arguments: .RS .XP \fITemplate\fP input (\fBstruct \fIspTemplate\fR) .br Data structure containing the pointers to four matrix elements. .XP \fIReal\fP input (spREAL) .br Real value to be added to the elements. .XP \fIImag\fP input (spREAL) .br Imaginary value to be added to the elements. .RE .Le .XS \n% \" Save section title for table of contents \n(sc.\n(ss: \fIspADD_COMPLEX_QUAD()\fP .XE .bp .nr ss 0 1 \" Reset subsection .RT .ne 1.5i .LG .B "\n+(sc: CONFIGURING SPARSE" .NL .XS \n% \" Save section title for table of contents \n(sc: Configuring \fISparse\fR .XE .PP \fISparse\fR has a extensive set of options and parameters that can be set at compile time to alter the personality of the program. They also are used to eliminate routines that are not needed so as to reduce the amount of memory required to hold the object code. These options and parameters consist of macros definitions and are contained in the file \fBspConfig.h\fR. To configure \fISparse\fR, \fBspConfig.h\fP must be edited and then \fISparse\fP must be recompiled. .PP Some terminology should be defined. The Markowitz row count is the number of non-zero elements in a row excluding the one being considered as pivot. There is one Markowitz row count for every row. The Markowitz column count is defined similarly for columns. The Markowitz product for an element is the product of its row and column counts. It is a measure of how much work would be required on the next step of the factorization if that element were chosen to be pivot. A small Markowitz product is desirable. For a more detailed explanation, see Kundert [kundert86]. .sp 2 .RT .ne 1i .LG .B "\n(sc.\n+(ss: Sparse Options" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Sparse Options .XE .KS .LP REAL .LP This specifies that the routines are expected to handle real systems of equations. The routines can be compiled to handle both real and complex systems at the same time, but there is a slight speed and memory advantage if the routines are complied to handle only real systems of equations. .KE .sp 0.6v .KS .LP spCOMPLEX .LP This specifies that the routines will be complied to handle complex systems of equations. .KE .sp 0.6v .KS .LP EXPANDABLE .LP Setting this compiler flag true makes the matrix expandable before it has been reordered. If the matrix is expandable, then if an element is added that would be considered out of bounds in the current matrix, the size of the matrix is increased to hold that element. As a result, the size of the matrix need not be known before the matrix is built. The matrix can be allocated with size zero and expanded. It is possible to expand the size of a matrix after it is been reordered if TRANSLATE and EXPANDABLE are both set true. .KE .sp 0.6v .KS .LP TRANSLATE .LP This option allows the set of external row and column numbers to be non-packed. In other words, the row and column numbers need not be contiguous. The priced paid for this flexibility is that when TRANSLATE is set true, the time required to initially build the matrix will be greater because the external row and column number must be translated into internal equivalents. This translation brings about other benefits though. First, the \fIspGetElement()\fR, \fIspGetAdmittance()\fR, \fIspGetQuad()\fR, and \fIspGetOnes()\fR routines may be used after the matrix has been factored. Further, elements, and even rows and columns, may be added to the matrix, and rows and columns may be deleted from the matrix, after it has been reordered. Note that when the set of row and column number is not a packed set, neither are the \fIRHS\fP and \fISolution\fP vectors. Thus the size of these vectors must be at least as large as the external size, which is the value of the largest given row or column numbers. .KE .sp 0.6v .KS .LP INITIALIZE .LP Causes the \fIspInitialize()\fR, \fIspGetInitInfo()\fR, and \fIspInstallInitInfo()\fR routines to be compiled. These routines allow the user to store and read one pointer in each nonzero element in the matrix. \fIspInitialize()\fR then calls a user specified function for each structural nonzero in the matrix, and includes this pointer as well as the external row and column numbers as arguments. This allows the user to write custom matrix and right-hand side vector initialization routines. .KE .sp 0.6v .KS .LP DIAGONAL_PIVOTING .LP Many matrices, and in particular node- and modified-node admittance matrices, tend to be nearly symmetric and nearly diagonally dominant. For these matrices, it is a good idea to select pivots from the diagonal. With this option enabled, this is exactly what happens, though if no satisfactory pivot can be found on the diagonal, an off-diagonal pivot will be used. If this option is disabled, \fISparse\fR does not preferentially search the diagonal. Because of this, \fISparse\fR has a wider variety of pivot candidates available, and so presumably fewer fill-ins will be created. However, the initial pivot selection process will take considerably longer. If working with node admittance matrices, or other matrices with a strong diagonal, it is probably best to use DIAGONAL_PIVOTING for two reasons. First, accuracy will be better because pivots will be chosen from the large diagonal elements, thus reducing the chance of growth and hence, roundoff. Second, a near optimal ordering will be chosen quickly. If the class of matrices you are working with does not have a strong diagonal, do not use DIAGONAL_PIVOTING, but consider using a larger threshold. When DIAGONAL_PIVOTING is turned off, the following options and constants are not used: MODIFIED_MARKOWITZ, MAX_MARKOWITZ_TIES, and TIES_MULTIPLIER. .KE .sp 0.6v .KS .LP ARRAY_OFFSET .LP This determines whether arrays start at an index of zero or one. This option is necessitated by the fact that standard C convention dictates that arrays begin with an index of zero but the standard mathematic convention states that arrays begin with an index of one. So if you prefer to start your arrays with zero, or you're calling \fISparse\fP from some other programming language, use an ARRAY_OFFSET of 0. Otherwise, use an ARRAY_OFFSET of 1. Note that if you use an offset of one, the arrays that you pass to \fISparse\fR must have an allocated length of one plus the external size of the matrix. ARRAY_OFFSET must be either 0 or 1, no other offsets are valid. .KE .sp 0.6v .KS .LP spSEPARATED_COMPLEX_VECTORS .LP This specifies the format for complex vectors. If this is set false then a complex vector is made up of one double sized array of spREALs in which the real and imaginary numbers are placed alternately in the array. In other words, the first entry would be \fIComplex[1].Real\fP, then comes \fIComplex[1].Imag\fP, then \fIComplex[2].Real\fP, etc. If spSEPARATED_COMPLEX_VECTORS is set true, then each complex vector is represented by two arrays of spREALs, one with the real terms, the other with the imaginary. .KE .sp 0.6v .KS .LP MODIFIED_MARKOWITZ .LP This specifies that the modified Markowitz method of pivot selection is to be used. The modified Markowitz method differs from standard Markowitz in two ways. First, under modified Markowitz, the search for a pivot can be terminated early if a adequate (in terms of sparsity) pivot candidate is found. Thus, when using modified Markowitz, the initial factorization can be faster, but at the expense of a suboptimal pivoting order that may slow subsequent factorizations. The second difference is in the way modified Markowitz breaks Markowitz ties. When two or more elements are pivot candidates and they all have the same Markowitz product, then the tie is broken by choosing the element that is best numerically. The numerically best element is the one with the largest ratio of its magnitude to the magnitude of the largest element in the same column, excluding itself. The modified Markowitz method results in marginally better accuracy. .KE .sp 0.6v .KS .LP DELETE .LP This specifies that the \fIspDeleteRowAndCol()\fP routine should be compiled. Note that for this routine to be compiled, both DELETE and TRANSLATE should be set true. .KE .sp 0.6v .KS .LP STRIP .LP This specifies that the \fIspStripFills()\fP routine should be compiled. .KE .sp 0.6v .KS .LP MODIFIED_NODAL .LP This specifies that the \fIspMNA_Preorder()\fR, the routine that preorders modified node admittance matrices, should be compiled. This routine results in greater speed and accuracy if used with this type of matrix. .KE .sp 0.6v .KS .LP QUAD_ELEMENT .LP This specifies that the routines that allow four related elements to be entered into the matrix at once should be compiled. The routines affected by QUAD_ELEMENT are \fIspGetAdmittance()\fP, \fIspGetQuad()\fP, and \fIspGetOnes()\fP. .KE .sp 0.6v .KS .LP TRANSPOSE .LP This specifies that \fIspSolveTranspose()\fR and perhaps \fIspMultTransposed()\fR, which operate on the matrix as if it was transposed, should be compiled. .KE .sp 0.6v .KS .LP SCALING .LP This specifies that the routine that performs scaling on the matrix should be complied. Scaling is not strongly supported. The routine to scale the matrix is provided, but no routines are provided to scale and descale the \fIRHS\fP and \fISolution\fP vectors. It is suggested that if scaling is desired, it only be performed when the pivot order is being chosen, which is done in \fIspOrderAndFactor()\fP. This, and when the condition number of the matrix is calculated with \fIspCondition()\fR, are the only times scaling has an effect. The scaling may then either be removed from the solution by the user or the scaled factored matrix may simply be thrown away. .KE .sp 0.6v .KS .LP DOCUMENTATION .LP This specifies that routines that are used to document the matrix, \fIspPrint()\fP, \fIspFileMatrix()\fP, \fIspFileVector()\fP, and \fIspFileStats()\fP, should be compiled. .KE .sp 0.6v .KS .LP DETERMINANT .LP This specifies that the \fIspDeterminant()\fR routine should be complied. .KE .sp 0.6v .KS .LP STABILITY .LP This specifies that \fIspLargestElement()\fR and \fIspRoundoff()\fR should be compiled. These routines are used to check the stability (and hence the quality of the pivoting) of the factorization by computing a bound on the size of the element is the matrix $bold E ~=~ bold A - bold LU$. If this bound is very high after applying \fIspOrderAndFactor()\fR, then the pivot threshold should be raised. If the bound increases greatly after using \fIspFactor()\fR, then the matrix should probably be reordered. .KE .sp 0.6v .KS .LP CONDITION .LP This specifies that \fIspCondition()\fR and \fIspNorm()\fR, the code that computes a good estimate of the condition number of the matrix, should be compiled. .KE .sp 0.6v .KS .LP PSEUDOCONDITION .LP This specifies that \fIspPseudoCondition()\fR, the code that computes a crude and easily fooled indicator of the ill-conditioning in the matrix, should be compiled. .KE .sp 0.6v .KS .LP MULTIPLICATION .LP This specifies that \fIspMultiply()\fR and perhaps \fIspMultTransposed()\fR, the routines that multiply an unfactored matrix by a vector, should be compiled. .KE .sp 0.6v .KS .LP FORTRAN .LP This specifies that the FORTRAN interface to Sparse1.3 should be compiled. The ARRAY_OFFSET option should be set to NO when interfacing to FORTRAN programs. .KE .sp 0.6v .KS .LP DEBUG .LP This specifies that additional error checking should be compiled. The type of errors checked are those that are common when the matrix routines are first integrated into a user's program. Once the routines have been integrated in and are running smoothly, this option should be turned off. With DEBUG enabled, \fISparse\fP is very defensive. If a \fISparse\fP routine is called improperly, a message will be printed describing the file and line number where the error was found and execution is aborted. One thing that \fISparse\fR is particularly picky about is calling certain functions after an error has occurred. If an error has occurred, do not call \fIspMNA_Preorder()\fR, \fIspScale()\fR, \fIspOrderAndFactor()\fR, \fIspFactor()\fR, \fIspSolve()\fR, or \fIspSolveTransposed()\fR until the error has been cleared by \fIspClear()\fR or \fIspInitialize()\fR. .KE .sp 0.6v .sp 2 .RT .ne 1i .LG .B "\n(sc.\n+(ss: Sparse Constants" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Sparse Constants .XE .PP These constants are used throughout the sparse matrix routines. They should be set to suit the type of matrices being solved. .sp 0.6v .KS .LP DEFAULT_THRESHOLD .LP The threshold used if the user enters an invalid threshold. Also the threshold used by \fIspFactor()\fP when calling \fIspOrderAndFactor()\fP. The default threshold should not be less than or equal to zero nor larger than one. .KE .sp 0.6v .KS .LP DIAG_PIVOTING_AS_DEFAULT .LP This indicates whether \fIspOrderAndFactor()\fP should use diagonal pivoting as default. This issue only arises when \fIspOrderAndFactor()\fP is called from \fIspFactor()\fP. .KE .sp 0.6v .KS .LP SPACE_FOR_ELEMENTS .LP This number multiplied by the size of the matrix equals the number of elements for which memory is initially allocated in \fIspCreate()\fP. .KE .sp 0.6v .KS .LP SPACE_FOR_FILL_INS .LP This number multiplied by the size of the matrix equals the number of elements for which memory is initially allocated and specifically reserved for fill-ins in \fIspCreate()\fP. .KE .sp 0.6v .KS .LP ELEMENTS_PER_ALLOCATION .LP The number of matrix elements requested from the \fImalloc\fP utility on each call to it. Setting this value greater than one reduces the amount of overhead spent in this system call. .KE .sp 0.6v .KS .LP MINIMUM_ALLOCATED_SIZE .LP The minimum allocated size of a matrix. Note that this does not limit the minimum size of a matrix. This just prevents having to resize a matrix many times if the matrix is expandable, large and allocated with an estimated size of zero. This number must not be less than one. .KE .sp 0.6v .KS .LP EXPANSION_FACTOR .LP The minimum increase in the allocated size of the matrix when it is expanded. This number must be greater than one but shouldn't be much larger than two. .KE .sp 0.6v .KS .LP MAX_MARKOWITZ_TIES .LP This number is used for two slightly different things, both of which relate to the search for the best pivot. First, it is the maximum number of elements that are Markowitz tied that will be sifted through when trying to find the one that is numerically the best. Second, it creates an upper bound on how large a Markowitz product can be before it eliminates the possibility of early termination of the pivot search. In other words, if the product of the smallest Markowitz product yet found and TIES_MULTIPLIER is greater than MAX_MARKOWITZ_TIES, then no early termination takes place. Set MAX_MARKOWITZ_TIES to some small value if no early termination of the pivot search is desired. An array of spREALs is allocated of size MAX_MARKOWITZ_TIES so it must be positive and shouldn't be too large. .KE .sp 0.6v .KS .LP TIES_MULTIPLIER .LP Specifies the number of Markowitz ties that are allowed to occur before the search for the pivot is terminated early. Set to some large value if no early termination of the pivot search is desired. This number is multiplied by the Markowitz product to determine how many ties are required for early termination. This means that more elements will be searched before early termination if a large number of fill-ins could be created by accepting what is currently considered the best choice for the pivot. Setting this number to zero effectively eliminates all pivoting, which should be avoided. This number must be positive. .KE .sp 0.6v .KS .LP DEFAULT_PARTITION .LP Which partition mode is used by \fIspPartition()\fR as default. Possibilities include: .RS .XP spDIRECT_PARTITION \(em each row used direct addressing, best for a few relatively dense matrices. .XP spINDIRECT_PARTITION \(em each row used indirect addressing, best for a few very sparse matrices. .XP spAUTO_PARTITION \(em direct or indirect addressing is chosen on a row-by-row basis, carries a large overhead, but speeds up both dense and sparse matrices, best if there is a large number of matrices that can use the same ordering. .RE .KE .sp 0.6v .KS .LP PRINTER_WIDTH .LP Gives the number of characters printable in one page width. Set to 80 for terminals and 132 for line printers. .KE .sp 2 .ne 1.5i .RT .LG .B "\n(sc.\n+(ss: Machine Constants" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Machine Constants .XE .LP These numbers .UL must be updated when the program is ported to a new machine. .sp 0.6v .KS .LP MACHINE_RESOLUTION .LP This is the smallest positive real double precision number $epsilon$ such that $ 1 ~ + ~ epsilon ~ != ~ 1 $. .KE .sp 0.6v .KS .LP LARGEST_REAL .LP The largest positive real number representable by a \fBdouble\fR. .KE .sp 0.6v .KS .LP SMALLEST_REAL .LP The smallest positive real number representable by a \fBdouble\fR. .KE .sp 0.6v .KS .LP LARGEST_SHORT_INTEGER .LP The largest positive integer representable by a \fBshort\fR. .KE .sp 0.6v .KS .LP LARGEST_LONG_INTEGER .LP The largest positive integer representable by a \fBlong\fR. .KE .bp .LP .nr ss 0 1 \" Reset subsection .RT .ne 1.5i .LG .B "\n+(sc: EXPORTS" .NL .XS \n% \" Save section title for table of contents \n(sc: Exports .XE .RT .ne 1i .LG .B "\n(sc.\n+(ss: Error Codes" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Error Codes .XE .PP Errors are indicated with a integer error code. Macros definitions for these error codes are set up and placed in the file \fBspMatrix.h\fP. They may be imported into the users program to give readable names to the possible matrix errors. The possible error codes and there corresponding macros are: .sp 0.25i .KS .LP spOKAY \(em 0 .LP No error has occurred. .KE .KS .LP spSMALL_PIVOT \(em 1 .LP When reordering the matrix, no element was found which satisfies the absolute threshold criteria. The largest element in the matrix was chosen as pivot. Nonfatal. .KE .KS .LP spZERO_DIAG \(em 2 .LP Fatal error. A zero was encountered on the diagonal of the matrix. This does not necessarily imply that the matrix is singular. When this error occurs, the matrix should be reconstructed and factored using \fIspOrderAndFactor()\fR. .KE .KS .LP spSINGULAR \(em 3 .LP Fatal error. Matrix is singular, so no unique solution exists. .KE .KS .LP spNO_MEMORY \(em 4 .LP Fatal error. Indicates that not enough memory is available from the system to handle the matrix. .KE .KS .LP spPANIC \(em 5 .LP Fatal error indicating that the routines are being asked to do something nonsensical or something they are not prepared for. This error may occur when the matrix is specified to be real and the routines are not compiled for real matrices, or when the matrix is specified to be complex and the routines are not compiled to handle complex matrices. .KE .KS .LP spFATAL \(em 2 .LP Not an error flag, but rather the dividing line between fatal errors and warnings. .KE .sp 2 .RT .ne 1i .LG .B "\n(sc.\n+(ss: Data Structures" .NL .XS \n% \" Save section title for table of contents \n(sc.\n(ss: Data Structures .XE .PP There is only one data structure that may need to be imported from \fISparse\fR by the user. This data structure is used to hold pointers to four related elements in matrix. It is used in conjunction with the routines .nf \fIspGetAdmittance()\fP \fIspGetOnes()\fP \fIspGetQuad()\fP .LP \fIspGetAdmittance()\fP, \fIspGetOnes()\fP, and \fIspGetQuad()\fP stuff the structure which is later used by the \fIspADD_QUAD()\fP macros. It is also possible for the user to collect four pointers returned by \fIspGetElement()\fP and stuff them into the template. The \fIspADD_QUAD()\fP macros add a value into \fIElement1\fP and \fIElement2\fP and subtract the value from \fIElement3\fP and \fIElement4\fP. The structure is: .KS .sp 0.25i .nf \fBstruct\fP \fIspTemplate\fP { spREAL *\fIElement1\fP; spREAL *\fIElement2\fP; spREAL *\fIElement3Negated\fP; spREAL *\fIElement4Negated\fP; }; .KE .bp .LP .nr ss 0 1 \" Reset subsection .RT .ne 1.5i .LG .B "\n+(sc: FORTRAN COMPATIBILITY" .NL .XS \n% \" Save section title for table of contents \n(sc: FORTRAN Compatibility .XE .PP The \fISparse1.3\fR package contains routines that interface to a calling program written in FORTRAN. Almost every externally available \fISparse1.3\fR routine has a counterpart defined with the same name except that the `sp' prefix is changed to `sf'. The \fIspADD_ELEMENT()\fR and \fIspADD_QUAD()\fR macros are also replaced with the \fIsfAdd1()\fR and \fIsfAdd4()\fR functions. .PP Any interface between two languages is going to have portibility problems, this one is no exception. To ease porting the FORTRAN interface file to different operating systems, the names of the interface functions can be easily redefined (search for `Routine Renaming' in \fBspFortran.c\fR). When interfacing to a FORTRAN program, the FORTRAN option should be set to YES and the ARRAY_OFFSET option should be set to NO (see \fBspConfig.h\fR). For details on the return value and argument list of a particular interface routine, see the file \fBspFortran.c\fR. .PP A simple example of a FORTRAN program that calls \fISparse\fR follows. .KS .B Example: .RS .nf integer matrix, error, sfCreate, sfGetElement, spFactor integer element(10) double precision rhs(4), solution(4) c c create matrix matrix = sfCreate(4,0,error) c c reserve elements element(1) = sfGetElement(matrix,1,1) element(2) = sfGetElement(matrix,1,2) element(3) = sfGetElement(matrix,2,1) element(4) = sfGetElement(matrix,2,2) element(5) = sfGetElement(matrix,2,3) element(6) = sfGetElement(matrix,3,2) element(7) = sfGetElement(matrix,3,3) element(8) = sfGetElement(matrix,3,4) element(9) = sfGetElement(matrix,4,3) element(10) = sfGetElement(matrix,4,4) c c clear matrix call sfClear(matrix) c c load matrix call sfAdd1Real(element(1), 2d0) call sfAdd1Real(element(2), \-1d0) call sfAdd1Real(element(3), \-1d0) call sfAdd1Real(element(4), 3d0) call sfAdd1Real(element(5), \-1d0) call sfAdd1Real(element(6), \-1d0) call sfAdd1Real(element(7), 3d0) call sfAdd1Real(element(8), \-1d0) call sfAdd1Real(element(9), \-1d0) call sfAdd1Real(element(10), 3d0) call sfprint(matrix, .false., .false., .true.) rhs(1) = 34d0 rhs(2) = 0d0 rhs(3) = 0d0 rhs(4) = 0d0 c c factor matrix error = sfFactor(matrix) c c solve matrix call sfSolve(matrix, rhs, solution) write (6, 10) solution(1), solution(2), solution(3), solution(4) 10 format (f 10.2) end .fi .KE .RE .bp .LP .nr ss 0 1 \" Reset subsection .RT .ne 1.5i .LG .B "\n+(sc: SPARSE TEST PROGRAM" .NL .XS \n% \" Save section title for table of contents \n(sc: \fISparse\fR Test Program .XE .PP The \fISparse\fR package includes a test program that is able to read matrix equations from text files and print their solution along with matrix statistics and timing information. The program can also generate files containing stripped versions of the unfactored and factored matrix suitable for plotting using standard plotting programs, such as the \s-1UNIX\s+1 graph and plot commands. .LP The \fISparse\fR test program is invoked using the following syntax. .ne 2.25i .IP \fBsparse\fR [\fIoptions\fR] [\fIfile1\fR] [\fIfile2\fR] ... .TS l l lw(4.5i). Options: \fB\-s\fR T{ Print solution only. T} \fB\-r\fI x\fR T{ Use \fIx\fR as relative threshold. T} \fB\-a\fI x\fR T{ Use \fIx\fR as absolute threshold. T} \fB\-n\fI n\fR T{ Print first \fIn\fR terms of solution vector. T} \fB\-i\fI n\fR T{ Repeat build/factor/solve \fIn\fR times for better timing results. T} \fB\-b\fI n\fR T{ Use column \fIn\fR of matrix as right-hand side vector. T} \fB\-p\fR T{ Create plot files ``\fIfilename\fB.bef\fR'' and ``\fIfilename\fB.aft\fR''. T} \fB\-c\fR T{ Use complete (as opposed to diagonal) pivoting. T} \fB\-x\fR T{ Treat real matrix as complex with imaginary part zero. T} \fB\-t\fR T{ Solve transposed system. T} \fB\-u\fR T{ Print usage message. T} .TE .LP The presence of certain options is dependent on whether the appropriate \fISparse\fR option has been enabled. .LP If no input files are specified, \fBsparse\fP reads from the standard input. The syntax of the input file is as follows. The matrix begins with one line of arbitrary text that acts as the label, followed by a line with the integer size of the matrix and either the \fBreal\fR or \fBcomplex\fR keywords. After the header is an arbitrary number of lines that describe the structural nonzeros in the matrix. These lines have the form \fIrow column data\fP, where \fIrow\fR and \fIcolumn\fR are integers and \fIdata\fP is either one real number for real matrices or a real/imaginary pair of numbers for complex matrices. Only one structural nonzero is described per line and the section ends when either \fIrow\fR or \fIcolumn\fR are zero. Following the matrix, an optional right-hand side vector can be described. The vector is given one element per line, the number of element must equal the size of the matrix. Only one matrix and one vector are allowed per file, and the vector, if given, must follow the matrix. .KS .B Example: .RS .nf mat0 \(em Simple matrix. 4 real 1 1 2.0 1 2 -1.0 2 1 -1.0 2 2 3.0 2 3 -1.0 3 2 -1.0 3 3 3.0 3 4 -1.0 4 3 -1.0 4 4 3.0 0 0 0.0 34.0 0.0 0.0 0.0 .fi .KE .RE .bp .LP .nr ss 0 1 \" Reset subsection .RT .ne 1.5i .LG .B "\n+(sc: SPARSE FILES" .NL .XS \n% \" Save section title for table of contents \n(sc: \fISparse\fR Files .XE .PP The following is a list of the files contained in the \fISparse\fR package and a brief description of their contents. Of the files, only \fBspConfig.h\fP is expected to be modified by the user and only \fBspMatrix.h\fP need be imported into the program that calls \fISparse\fR. .KS .LP \fBspAlloc.c\fR .LP This file contains the routines for allocating and deallocating objects associated with the matrices, including the matrices themselves. .XP \(bu User accessible functions contained in this module: .nf .I spCreate() spDestroy() spError() spWhereSingular() spGetSize() spSetReal() spSetComplex() spFillinCount() spElementCount() .R .KE .KS .LP \fBspBuild.c\fR .LP This file contains the routines for clearing and loading the matrix. .XP \(bu User accessible functions contained in this module: .nf .I spClear() spGetAdmittance() spGetElement() spGetInitInfo() spGetOnes() spGetQuad() spInitialize() spInstallInitInfo() .R .KE .KS .LP \fBspConfig.h\fR .LP This file contains the options that are used to customize the package. For example, it is possible to specify whether only real or complex systems of equations are to be solved. Also included in this file are the various constants used by the \fISparse\fR package, such as the amount of memory initially allocated for each matrix and the largest real number represented by the machine. The user is expected to modify this file to maximize the performance of the routines with his/her matrices. .KE .KS .LP \fBspDefs.h\fR .LP This module contains common data structure definitions and macros for the sparse matrix routines. These definitions are meant to remain hidden from the program that calls the sparse matrix routines. .KE .KS .LP \fBspDoc\fR .LP This reference manual. \fBspDoc\fP contains the manual in a form that is readable on-line and \fBspDoc.ms\fP contains the manual in a form that is suitable for input into the text formatting program \fItroff\fP using the -ms macros. .KE .KS .LP \fBspFactor.c\fR .LP This file contains the routines for factoring matrices into LU form. .XP \(bu User accessible functions contained in this module: .nf .I spFactor() spOrderAndFactor() spPartition() .R .KE .KS .LP \fBspFortran.c\fR .LP This file contains the routines for interfacing \fISparse1.3\fR to a program written in FORTRAN. The function and argument lists of the routines in this file are almost identical to their C equivalents except that they are suitable for calling from a FORTRAN program. The names of these routines use the `sf' prefix to distinguish them from their C counterparts. .XP \(bu User accessible functions contained in this module: .nf .I sfAdd1Complex() sfAdd1Imag() sfAdd1Real() sfAdd4Complex() sfAdd4Imag() sfAdd4Real() sfClear() sfCondition() sfCreate() sfDeleteRowAndCol() sfDestroy() sfDeterminant() sfElementCount() sfError() sfFactor() sfFileMatrix() sfFileStats() sfFileVector() sfFillinCount() sfGetAdmittance() sfGetElement() sfGetOnes() sfGetQuad() sfGetSize() sfLargestElement() sfMNA_Preorder() sfMultTransposed() sfMultiply() sfNorm() sfOrderAndFactor() sfPartition() sfPrint() sfPseudoCondition() sfRoundoff() sfScale() sfSetComplex() sfSetReal() sfSolve() sfSolveTransposed() sfStripFills() sfWhereSingular() .R .KE .KS .LP \fBspMatrix.h\fR .NL .LP This file contains definitions that are useful to the calling program. In particular, this file contains error keyword definitions, some macro functions that are used to quickly enter data into the matrix, the definition of a data structure that acts as a template for entering admittances into the matrix, and the type declarations of the various \fISparse\fR functions. .KE .KS .LP \fBspOutput.c\fR .LP This file contains the output-to-file and output-to-screen routines for the matrix package. They are capable of outputting the matrix in either a form readable by people or a form readable by the \fISparse\fR test program. .XP \(bu User accessible functions contained in this module: .nf .I spFileMatrix() spFileStats() spFileVector() spPrint() .R .KE .KS .LP \fBspRevision\fR .LP The history of updates for the program. This file also includes ordering information for the \fISparse\fR package. .KE .KS .LP \fBspSolve.c\fR .LP This module contains the forward and backward substitution routines. .XP \(bu User accessible functions contained in this module: .nf .I spSolve() spSolveTransposed() .R .KE .KS .LP \fBspTest.c\fR .LP This module contains a test program for the sparse matrix routines. It is able to read matrices from files and solve them. Because of the large number of options and capabilities built into \fISparse\fR, it is impossible to have one test routine thoroughly exercise \fISparse\fR. Thus, emphasis is on exercising as many capabilities as is reasonable while also providing a useful tool. .KE .KS .LP \fBspUtil.c\fR .LP This module contains various optional utility routines. .XP \(bu User accessible functions contained in this module: .nf .I spCondition() spDeleteRowAndCol() spDeterminant() spLargestElement() spMNA_Preorder() spMultiply() spMultTransposed() spNorm() spPseudoCondition() spRoundoff() spScale() spStripFills() .R .KE .KS .LP \fBMakefile\fR .LP This file is used in conjunction with the UNIX program \fBmake\fR to compile the matrix routines and their test program. .KE .KS .LP .B make.com .LP This file is used to automatically compile \fISparse\fR under the VMS operating system. It needs to modified slightly before being used, see the installation notes. .KE .bp .LP .LG .B "REFERENCES" .NL .XS \n% References .XE .KS .IP [duff86] 15 I. S. Duff, A. M. Erisman, J. K. Reid. \fIDirect Methods for Sparse Matrices\fP. Oxford University Press, 1986. .KE .KS .IP [golub86] 15 G. H. Golub, C. F. V. Van Loan. \fIMatrix Computations\fP. The Johns Hopkins University Press, 1983. .KE .KS .IP [kundert86] 15 Kenneth S. Kundert. Sparse matrix techniques. In \fICircuit Analysis, Simulation and Design\fP, Albert Ruehli (editor). North-Holland, 1986. .KE .KS .IP [strang80] 15 Gilbert Strang. \fILinear Algebra and Its Applications\fP. Academic Press, 1980. .KE .sp 2 .LG .B Acknowledgements .NL .ad .PP We would like to acknowledge and thank the those people that contributed ideas that were incorporated into \fISparse\fP. In particular, Jacob White, Kartikeya Mayaram, Don Webber, Tom Quarles, Howard Ko and Beresford Parlett. .ds CH \" stop printing page number .bp .PX .