---

spMatrix.h File Reference

#include "spConfig.h"

Go to the source code of this file.

Compounds
struct	spTemplate
Defines
#define	spOKAY   0
#define	spSMALL_PIVOT   1
#define	spZERO_DIAG   2
#define	spSINGULAR   3
#define	spMANGLED   4
#define	spNO_MEMORY   5
#define	spPANIC   6
#define	spFATAL   2
#define	spREAL   double
#define	spDEFAULT_PARTITION   0
#define	spDIRECT_PARTITION   1
#define	spINDIRECT_PARTITION   2
#define	spAUTO_PARTITION   3
#define	spADD_REAL_ELEMENT(element, real)   *(element) += real
#define	spADD_IMAG_ELEMENT(element, imag)   *(element+1) += imag
#define	spADD_COMPLEX_ELEMENT(element, real, imag)
#define	spADD_REAL_QUAD(template, real)
#define	spADD_IMAG_QUAD(template, imag)
#define	spADD_COMPLEX_QUAD(template, real, imag)
Typedefs
typedef spGenericPtr	spMatrix
typedef spREAL	spElement
typedef int	spError
Functions
spcEXTERN void	spClear (spMatrix)
spcEXTERN spREAL	spCondition (spMatrix, spREAL, int *)
spcEXTERN spMatrix	spCreate (int, int, spError *)
spcEXTERN void	spDeleteRowAndCol (spMatrix, int, int)
spcEXTERN void	spDestroy (spMatrix)
spcEXTERN int	spElementCount (spMatrix)
spcEXTERN spError	spErrorState (spMatrix)
spcEXTERN void	spErrorMessage (spMatrix, FILE *, char *)
spcEXTERN spError	spFactor (spMatrix)
spcEXTERN int	spFileMatrix (spMatrix, char *, char *, int, int, int)
spcEXTERN int	spFileStats (spMatrix, char *, char *)
spcEXTERN int	spFillinCount (spMatrix)
spcEXTERN spElement *	spFindElement (spMatrix, int, int)
spcEXTERN spError	spGetAdmittance (spMatrix, int, int, struct spTemplate *)
spcEXTERN spElement *	spGetElement (spMatrix, int, int)
spcEXTERN spGenericPtr	spGetInitInfo (spElement *)
spcEXTERN spError	spGetOnes (spMatrix, int, int, int, struct spTemplate *)
spcEXTERN spError	spGetQuad (spMatrix, int, int, int, int, struct spTemplate *)
spcEXTERN int	spGetSize (spMatrix, int)
spcEXTERN int	spInitialize (spMatrix, int(*pInit)(spElement *, spGenericPtr, int, int))
spcEXTERN void	spInstallInitInfo (spElement *, spGenericPtr)
spcEXTERN spREAL	spLargestElement (spMatrix)
spcEXTERN void	spMNA_Preorder (spMatrix)
spcEXTERN spREAL	spNorm (spMatrix)
spcEXTERN spError	spOrderAndFactor (spMatrix, spREAL[], spREAL, spREAL, int)
spcEXTERN void	spPartition (spMatrix, int)
spcEXTERN void	spPrint (spMatrix, int, int, int)
spcEXTERN spREAL	spPseudoCondition (spMatrix)
spcEXTERN spREAL	spRoundoff (spMatrix, spREAL)
spcEXTERN void	spScale (spMatrix, spREAL[], spREAL[])
spcEXTERN void	spSetComplex (spMatrix)
spcEXTERN void	spSetReal (spMatrix)
spcEXTERN void	spStripFills (spMatrix)
spcEXTERN void	spWhereSingular (spMatrix, int *, int *)
spcEXTERN void	spDeterminant (spMatrix, int *, spREAL *, spREAL *)
spcEXTERN int	spFileVector (spMatrix, char *, spREAL[])
spcEXTERN void	spMultiply (spMatrix, spREAL[], spREAL[])
spcEXTERN void	spMultTransposed (spMatrix, spREAL[], spREAL[])
spcEXTERN void	spSolve (spMatrix, spREAL[], spREAL[])
spcEXTERN void	spSolveTransposed (spMatrix, spREAL[], spREAL[])

---

Detailed Description

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 and the type definition of a data structure that acts as a template for entering admittances into the matrix. Also included is the type definitions for the various functions available to the user.

Objects that begin with the spc prefix are considered private and should not be used.

Author:

Kenneth S. Kundert <kundert@users.sourceforge.net>

---

Define Documentation

#define spADD_COMPLEX_ELEMENT (  element, real, imag    )

Value: { *(element) += real; \ *(element+1) += imag; \ } Macro function that adds data to a complex element in the matrix by a pointer.

#define spADD_COMPLEX_QUAD (  template, real, imag    )

Value: { *((template).Element1) += real; \ *((template).Element2) += real; \ *((template).Element3Negated) -= real; \ *((template).Element4Negated) -= real; \ *((template).Element1+1) += imag; \ *((template).Element2+1) += imag; \ *((template).Element3Negated+1) -= imag; \ *((template).Element4Negated+1) -= imag; \ } Macro function that adds data to each of the four complex matrix elements specified by the given template.

#define spADD_IMAG_ELEMENT (  element, imag    )     *(element+1) += imag

Macro function that adds data to a imaginary element in the matrix by a pointer.

#define spADD_IMAG_QUAD (  template, imag    )

Value: { *((template).Element1+1) += imag; \ *((template).Element2+1) += imag; \ *((template).Element3Negated+1) -= imag; \ *((template).Element4Negated+1) -= imag; \ } Macro function that adds data to each of the four imaginary matrix elements specified by the given template.

#define spADD_REAL_ELEMENT (  element, real    )     *(element) += real

Macro function that adds data to a real element in the matrix by a pointer.

#define spADD_REAL_QUAD (  template, real    )

Value: { *((template).Element1) += real; \ *((template).Element2) += real; \ *((template).Element3Negated) -= real; \ *((template).Element4Negated) -= real; \ } Macro function that adds data to each of the four real matrix elements specified by the given template.

#define spAUTO_PARTITION   3

Partition code for spPartition(). Indicates that Sparse should chose the best partition for each row based on some simple rules. This is generally preferred. See also: spPartition()

#define spDEFAULT_PARTITION   0

Partition code for spPartition(). Indicates that the default partitioning mode should be used. See also: spPartition()

#define spDIRECT_PARTITION   1

Partition code for spPartition(). Indicates that all rows should be placed in the direct addressing partition. See also: spPartition()

#define spFATAL   2

Error code that is not an error flag, but rather the dividing line between fatal errors and warnings.

#define spINDIRECT_PARTITION   2

Partition code for spPartition(). Indicates that all rows should be placed in the indirect addressing partition. See also: spPartition()

#define spMANGLED   4

Fatal error code that indicates that, matrix has been mangled, results of requested operation are garbage.

#define spNO_MEMORY   5

Fatal error code that indicates that not enough memory is available.

#define spOKAY   0

Error code that indicates that no error has occurred.

#define spPANIC   6

Fatal error code that indicates that the routines are not prepared to handle the matrix that has been requested. This 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.

#define spREAL   double

Defines the precision of the arithmetic used by Sparse will use. Double precision is suggested as being most appropriate for circuit simulation and for C. However, it is possible to change spREAL to a float for single precision arithmetic. Note that in C, single precision arithmetic is often slower than double precision. Sparse internally refers to spREALs as RealNumbers.

#define spSINGULAR   3

Fatal error code that indicates that, matrix is singular, so no unique solution exists.

#define spSMALL_PIVOT   1

Non-fatal error code that indicates that, when reordering the matrix, no element was found that satisfies the absolute threshold criteria. The largest element in the matrix was chosen as pivot.

#define spZERO_DIAG   2

Fatal error code that indicates that, a zero was encountered on the diagonal the matrix. This does not necessarily imply that the matrix is singular. When this error occurs, the matrix should be reconstructed and factored using spOrderAndFactor().

---

Typedef Documentation

typedef spREAL spElement

Declares the type of the a pointer to a matrix element.

typedef int spError

Declares the type of the Sparse error codes.

typedef spGenericPtr spMatrix

Declares the type of the a pointer to a matrix.

---

Function Documentation

spcEXTERN void spClear (  spMatrix    eMatrix )

Sets every element of the matrix to zero and clears the error flag. Parameters: eMatrix  Pointer to matrix that is to be cleared.

spcEXTERN spREAL spCondition (  spMatrix    eMatrix, spREAL    NormOfMatrix, int *    pError )

Computes an estimate of the condition number using a variation on the LINPACK condition number estimation algorithm. This quantity is an indicator 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 spOrderAndFactor() or spFactor() and before it is cleared by spClear() or spInitialize(). 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. References: A.K. Cline, C.B. Moler, G.W. Stewart, J.H. Wilkinson. An estimate for the condition number of a matrix. SIAM Journal on Numerical Analysis. Vol. 16, No. 2, pages 368-375, April 1979. J.J. Dongarra, C.B. Moler, J.R. Bunch, G.W. Stewart. LINPACK User's Guide. SIAM, 1979. Roger G. Grimes, John G. Lewis. Condition number estimation for sparse matrices. SIAM Journal on Scientific and Statistical Computing. Vol. 2, No. 4, pages 384-388, December 1981. Dianne Prost O'Leary. Estimating matrix condition numbers. SIAM Journal on Scientific and Statistical Computing. Vol. 1, No. 2, pages 205-209, June 1980. Returns : The reciprocal of the condition number. If the matrix was singular, zero is returned. Parameters: eMatrix  Pointer to the matrix. NormOfMatrix  The L-infinity norm of the unfactored matrix as computed by spNorm(). pError  Used to return error code. Possible errors include spSINGULAR or spNO_MEMORY.

spcEXTERN spMatrix spCreate (  int    Size, int    Complex, spError *    pError )

Allocates and initializes the data structures associated with a matrix. Returns : A pointer to the matrix is returned cast into spMatrix (typically a pointer to a void). 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. Parameters: Size  Size of matrix or estimate of size of matrix if matrix is EXPANDABLE. Complex  Type of matrix. If Complex 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 an spPANIC error will occur. Further note that if a matrix will be both real and complex, it must be specified here as being complex. pError  Returns error flag, needed because function spErrorState() will not work correctly if spCreate() returns NULL. Possible errors include spNO_MEMORY and spPANIC.

spcEXTERN void spDeleteRowAndCol (  spMatrix    eMatrix, int    Row, int    Col )

Deletes a row and a column from a matrix. Sparse will abort if an attempt is made to delete a row or column that doesn't exist. Parameters: eMatrix  Pointer to the matrix in which the row and column are to be deleted. Row  Row to be deleted. Col  Column to be deleted.

spcEXTERN void spDestroy (  spMatrix    eMatrix )

Destroys a matrix and frees all memory associated with it. Parameters: eMatrix  Pointer to the matrix frame which is to be destroyed.

spcEXTERN void spDeterminant (  spMatrix    eMatrix, int *    pExponent, spREAL *    pDeterminant, spREAL *    piDeterminant )

This routine in capable of calculating the determinant of the matrix once the LU factorization has been performed. Hence, only use this routine after spFactor() and before spClear(). The determinant equals the product of all the diagonal elements of the lower triangular matrix L, except that this product may need negating. Whether the product or the negative product equals the determinant is determined by the number of row and column interchanges performed. 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 determinant is scaled to a reasonable value and the logarithm of the scale factor is returned. Parameters: eMatrix  A pointer to the matrix for which the determinant is desired. pExponent  The logarithm base 10 of the scale factor for the determinant. To find the actual determinant, Exponent should be added to the exponent of Determinant. pDeterminant  The real portion of the determinant. This number is scaled to be greater than or equal to 1.0 and less than 10.0. piDeterminant  The imaginary portion of the determinant. When the matrix is real this pointer need not be supplied, nothing will be returned. This number is scaled to be greater than or equal to 1.0 and less than 10.0.

spcEXTERN int spElementCount (  spMatrix    eMatrix )

This function returns the total number of elements (including fill-ins) that currently exists in a matrix. Parameters: eMatrix  Pointer to matrix.

spcEXTERN void spErrorMessage (  spMatrix    eMatrix, FILE *    Stream, char *    Originator )

This routine prints a short message describing the error error state of sparse. No message is produced if there is no error. The error state is cleared. Parameters: eMatrix  Matrix for which the error message is to be printed. Stream  Stream to which the error message is to be printed. Originator  Name of originator of error message. If NULL, `sparse' is used. If zero-length string, no originator is printed.

spcEXTERN spError spErrorState (  spMatrix    eMatrix )

This function returns the error status of the given matrix. Returns : The error status of the given matrix. Parameters: eMatrix  The pointer to the matrix for which the error status is desired.

spcEXTERN spError spFactor (  spMatrix    eMatrix )

This routine is the companion routine to spOrderAndFactor(). Unlike spOrderAndFactor(), spFactor() cannot change the ordering. It is also faster than spOrderAndFactor(). The standard way of using these two routines is to first use spOrderAndFactor() for the initial factorization. For subsequent factorizations, spFactor() is used if there is some assurance that little growth will occur (say for example, that the matrix is diagonally dominant). If spFactor() is called for the initial factorization of the matrix, then spOrderAndFactor() is automatically called with the default threshold. This routine uses "row at a time" LU factorization. Pivots are associated with the lower triangular matrix and the diagonals of the upper triangular matrix are ones. Returns : The error code is returned. Possible errors are spNO_MEMORY, spSINGULAR, spZERO_DIAG and spSMALL_PIVOT. Error is cleared upon entering this function. Parameters: eMatrix  Pointer to matrix. See also: spOrderAndFactor()

spcEXTERN int spFileMatrix (  spMatrix    eMatrix, char *    File, char *    Label, int    Reordered, int    Data, int    Header )

Writes matrix to file in format suitable to be read back in by the matrix test program. Returns : One is returned if routine was successful, otherwise zero is returned. The calling function can query errno (the system global error variable) as to the reason why this routine failed. Parameters: eMatrix  Pointer to matrix. File  Name of file into which matrix is to be written. Label  String that is transferred to file and is used as a label. Reordered  Specifies whether matrix should be output in reordered form, or in original order. Data  Indicates that the element values should be output along with the indices for each element. This parameter must be true if matrix is to be read by the sparse test program. Header  Indicates that header is desired. This parameter must be true if matrix is to be read by the sparse test program.

spcEXTERN int spFileStats (  spMatrix    eMatrix, char *    File, char *    Label )

Writes useful information concerning the matrix to a file. Should be executed after the matrix is factored. Returns : One is returned if routine was successful, otherwise zero is returned. The calling function can query errno (the system global error variable) as to the reason why this routine failed. Parameters: eMatrix  Pointer to matrix. File  Name of file into which matrix is to be written. Label  String that is transferred to file and is used as a label.

spcEXTERN int spFileVector (  spMatrix    eMatrix, char *    File, spREAL    RHS[] )

Writes vector to file in format suitable to be read back in by the matrix test program. This routine should be executed after the function spFileMatrix. Returns : One is returned if routine was successful, otherwise zero is returned. The calling function can query errno (the system global error variable) as to the reason why this routine failed. Parameters: eMatrix  Pointer to matrix. File  Name of file into which matrix is to be written. RHS  Right-hand side vector. This is only the real portion if spSEPARATED_COMPLEX_VECTORS is true. iRHS  Right-hand side vector, imaginary portion. Not necessary if matrix is real or if spSEPARATED_COMPLEX_VECTORS is set false. iRHS is a macro that replaces itself with `, iRHS' if the options spCOMPLEX and spSEPARATED_COMPLEX_VECTORS are set, otherwise it disappears without a trace.

spcEXTERN int spFillinCount (  spMatrix    eMatrix )

This function returns the number of fill-ins that currently exists in a matrix. Parameters: eMatrix  Pointer to matrix.

spcEXTERN spElement* spFindElement (  spMatrix    eMatrix, int    Row, int    Col )

This routine is used to find an element given its indices. It will not create it if it does not exist. Returns : A pointer to the desired element, or NULL if it does not exist. Parameters: eMatrix  Pointer to matrix. Row  Row index for element. Col  Column index for element. See also: spGetElement()

spcEXTERN spError spGetAdmittance (  spMatrix    Matrix, int    Node1, int    Node2, struct spTemplate *    Template )

Performs same function as spGetElement() except rather than one element, all four matrix elements for a floating two terminal admittance component are added. This routine also works if component is grounded. Positive elements are placed at [Node1,Node2] and [Node2,Node1]. This routine is only to be used after spCreate() and before spMNA_Preorder(), spFactor() or spOrderAndFactor(). Returns : Error code. Possible errors include spNO_MEMORY. Error is not cleared in this routine. Parameters: Matrix  Pointer to the matrix that component is to be entered in. Node1  Row and column indices for elements. Must be in the range of [0..Size] unless the options EXPANDABLE or TRANSLATE are used. Node zero is the ground node. In no case may Node1 be less than zero. Node2  Row and column indices for elements. Must be in the range of [0..Size] unless the options EXPANDABLE or TRANSLATE are used. Node zero is the ground node. In no case may Node2 be less than zero. Template  Collection of pointers to four elements that are later used to directly address elements. User must supply the template, this routine will fill it.

spcEXTERN spElement* spGetElement (  spMatrix    eMatrix, int    Row, int    Col )

Finds element [Row,Col] and returns a pointer to it. If element is not found then it is created and spliced into matrix. This routine is only to be used after spCreate() and before spMNA_Preorder(), spFactor() or spOrderAndFactor(). Returns a pointer to the real portion of an spElement. This pointer is later used by spADD_xxx_ELEMENT to directly access element. Returns : Returns a pointer to the element. This pointer is then used to directly access the element during successive builds. Parameters: eMatrix  Pointer to the matrix that the element is to be added to. Row  Row index for element. Must be in the range of [0..Size] unless the options EXPANDABLE or TRANSLATE are used. Elements placed in row zero are discarded. In no case may Row be less than zero. Col  Column index for element. Must be in the range of [0..Size] unless the options EXPANDABLE or TRANSLATE are used. Elements placed in column zero are discarded. In no case may Col be less than zero. See also: spFindElement()

spcEXTERN spGenericPtr spGetInitInfo (  spElement *    pElement )

This function returns a pointer to a data structure that is used to contain initialization information to a matrix element. Returns : The pointer to the initialiation information data structure that is associated with a particular matrix element. Parameters: pElement  Pointer to the matrix element. See also: spInitialize()

spcEXTERN spError spGetOnes (  spMatrix    Matrix, int    Pos, int    Neg, int    Eqn, struct spTemplate *    Template )

Addition of four structural ones to matrix by index. Performs similar function to spGetQuad() except this routine is meant for components that do not have an admittance representation. The following stamp is used: Pos Neg Eqn Pos [ . . 1 ] Neg [ . . -1 ] Eqn [ 1 -1 . ] Returns : Error code. Possible errors include spNO_MEMORY. Error is not cleared in this routine. Parameters: Matrix  Pointer to the matrix that component is to be entered in. Pos  See stamp above. Must be in the range of [0..Size] unless the options EXPANDABLE or TRANSLATE are used. Zero is the ground row. In no case may Pos be less than zero. Neg  See stamp above. Must be in the range of [0..Size] unless the options EXPANDABLE or TRANSLATE are used. Zero is the ground row. In no case may Neg be less than zero. Eqn  See stamp above. Must be in the range of [0..Size] unless the options EXPANDABLE or TRANSLATE are used. Zero is the ground row. In no case may Eqn be less than zero. Template  Collection of pointers to four elements that are later used to directly address elements. User must supply the template, this routine will fill it.

spcEXTERN spError spGetQuad (  spMatrix    Matrix, int    Row1, int    Row2, int    Col1, int    Col2, struct spTemplate *    Template )

Similar to spGetAdmittance(), except that spGetAdmittance() only handles 2-terminal components, whereas spGetQuad() 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. spGetQuad() adds four elements to the matrix. Positive elements occur at [Row1,Col1] [Row2,Col2] while negative elements occur at [Row1,Col2] and [Row2,Col1]. The routine works fine if any of the rows and columns are zero. This routine is only to be used after spCreate() and before spMNA_Preorder(), spFactor() or spOrderAndFactor() unless TRANSLATE is set true. Returns : Error code. Possible errors include spNO_MEMORY. Error is not cleared in this routine. Parameters: Matrix  Pointer to the matrix that component is to be entered in. Row1  First row index for elements. Must be in the range of [0..Size] unless the options EXPANDABLE or TRANSLATE are used. Zero is the ground row. In no case may Row1 be less than zero. Row2  Second row index for elements. Must be in the range of [0..Size] unless the options EXPANDABLE or TRANSLATE are used. Zero is the ground row. In no case may Row2 be less than zero. Col1  First column index for elements. Must be in the range of [0..Size] unless the options EXPANDABLE or TRANSLATE are used. Zero is the ground column. In no case may Col1 be less than zero. Col2  Second column index for elements. Must be in the range of [0..Size] unless the options EXPANDABLE or TRANSLATE are used. Zero is the ground column. In no case may Col2 be less than zero. Template  Collection of pointers to four elements that are later used to directly address elements. User must supply the template, this routine will fill it.

spcEXTERN int spGetSize (  spMatrix    eMatrix, int    External )

Returns the size of the matrix. Either the internal or external size of the matrix is returned. Parameters: eMatrix  Pointer to matrix. External  If External is set true, the external size , i.e., the value of the largest external row or column number encountered is returned. Otherwise the true size of the matrix is returned. These two sizes may differ if the TRANSLATE option is set true.

spcEXTERN void spInstallInitInfo (  spElement *    pElement, spGenericPtr    pInitInfo )

This function installs a pointer to a data structure that is used to contain initialization information to a matrix element. It is is then used by spInitialize() to initialize the matrix. Parameters: pElement  Pointer to matrix element. pInitInfo  Pointer to the data structure that will contain initialiation information. See also: spInitialize()

spcEXTERN spREAL spLargestElement (  spMatrix    eMatrix )

This routine, along with spRoundoff(), are used to gauge the stability of a factorization. If the factorization is determined to be too unstable, then the matrix should be reordered. The routines compute quantities that are needed in the computation of a bound on the error attributed to any one element in the matrix during the factorization. In other words, there is a matrix of error terms such that . This routine finds a bound on . Erisman & Reid [1] showed that , where is the machine rounding unit, where the max is taken over every row , column , and step , and is the number of multiplications required in the computation of if or otherwise. Barlow [2] showed that where . spLargestElement() finds the magnitude on the largest element in the matrix. If the matrix has not yet been factored, the largest element is found by direct search. If the matrix is factored, a bound on the largest element in any of the reduced submatrices is computed using Barlow with and . The ratio of these two numbers 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 spFactor(), reconstruct the matrix and refactor using spOrderAndFactor(). If a large growth is encountered after using spOrderAndFactor(), refactor using spOrderAndFactor() with the pivot threshold increased, say to 0.1. Using only the size of the matrix as an upper bound on and Barlow's bound, the user can estimate the size of the matrix error terms using the bound of Erisman and Reid. spRoundoff() computes a tighter bound (with more work) based on work by Gear [3], where is the threshold and is the maximum number of off-diagonal elements in any row of . The expensive part of computing this bound is determining the maximum number of off-diagonals in , which changes only when the order of the matrix changes. This number is computed and saved, and only recomputed if the matrix is reordered. [1] A. M. Erisman, J. K. Reid. Monitoring the stability of the triangular factorization of a sparse matrix. Numerische Mathematik. Vol. 22, No. 3, 1974, pp 183-186. [2] J. L. Barlow. A note on monitoring the stability of triangular decomposition of sparse matrices. "SIAM Journal of Scientific and Statistical Computing." Vol. 7, No. 1, January 1986, pp 166-168. [3] I. S. Duff, A. M. Erisman, J. K. Reid. "Direct Methods for Sparse Matrices." Oxford 1986. pp 99. Returns : If matrix is not factored, 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. Parameters: eMatrix  Pointer to the matrix.

spcEXTERN void spMNA_Preorder (  spMatrix    eMatrix )

This routine massages modified node admittance matrices to remove zeros from the diagonal. It takes advantage of the fact that the row and column associated with a zero diagonal usually have structural ones placed symmetricly. This routine should be used only on modified node admittance matrices and should be executed after the matrix has been built but before the factorization begins. It should be executed for the initial factorization only and should be executed before the rows have been linked. Thus it should be run before using spScale(), spMultiply(), spDeleteRowAndCol(), or spNorm(). This routine exploits the fact that the structural ones are placed in the matrix in symmetric twins. For example, the stamps for grounded and a floating voltage sources are grounded: floating: [ x x 1 ] [ x x 1 ] [ x x ] [ x x -1 ] [ 1 ] [ 1 -1 ] Notice for the grounded source, there is one set of twins, and for the floating, there are two sets. We remove the zero from the diagonal by swapping the rows associated with a set of twins. For example: grounded: floating 1: floating 2: [ 1 ] [ 1 -1 ] [ x x 1 ] [ x x ] [ x x -1 ] [ 1 -1 ] [ x x 1 ] [ x x 1 ] [ x x -1 ] It is important to deal with any zero diagonals that only have one set of twins before dealing with those that have more than one because swapping row destroys the symmetry of any twins in the rows being swapped, which may limit future moves. Consider [ x x 1 ] [ x x -1 1 ] [ 1 -1 ] [ 1 ] There is one set of twins for diagonal 4 and two for diagonal 3. Dealing with diagonal 4 first requires swapping rows 2 and 4. [ x x 1 ] [ 1 ] [ 1 -1 ] [ x x -1 1 ] We can now deal with diagonal 3 by swapping rows 1 and 3. [ 1 -1 ] [ 1 ] [ x x 1 ] [ x x -1 1 ] And we are done, there are no zeros left on the diagonal. However, if we originally dealt with diagonal 3 first, we could swap rows 2 and 3 [ x x 1 ] [ 1 -1 ] [ x x -1 1 ] [ 1 ] Diagonal 4 no longer has a symmetric twin and we cannot continue. So we always take care of lone twins first. When none remain, we choose arbitrarily a set of twins for a diagonal with more than one set and swap the rows corresponding to that twin. We then deal with any lone twins that were created and repeat the procedure until no zero diagonals with symmetric twins remain. In this particular implementation, columns are swapped rather than rows. The algorithm used in this function was developed by Ken Kundert and Tom Quarles. Parameters: eMatrix  Pointer to the matrix to be preordered.

spcEXTERN void spMultiply (  spMatrix    eMatrix, spREAL    RHS[], spREAL    Solution[] )

Multiplies matrix by solution vector to find source vector. Assumes matrix has not been factored. This routine can be used as a test to see if solutions are correct. It should not be used before spMNA_Preorder(). Parameters: eMatrix  Pointer to the matrix. RHS  RHS is the right hand side. This is what is being solved for. Solution  Solution is the vector being multiplied by the matrix. iRHS  iRHS is the imaginary portion of the right hand side. This is what is being solved for. This is only necessary if the matrix is complex and spSEPARATED_COMPLEX_VECTORS is true. iSolution  iSolution is the imaginary portion of the vector being multiplied by the matrix. This is only necessary if the matrix is complex and spSEPARATED_COMPLEX_VECTORS is true.

spcEXTERN void spMultTransposed (  spMatrix    eMatrix, spREAL    RHS[], spREAL    Solution[] )

Multiplies transposed matrix by solution vector to find source vector. Assumes matrix has not been factored. This routine can be used as a test to see if solutions are correct. It should not be used before spMNA_Preorder(). Parameters: eMatrix  Pointer to the matrix. RHS  RHS is the right hand side. This is what is being solved for. Solution  Solution is the vector being multiplied by the matrix. iRHS  iRHS is the imaginary portion of the right hand side. This is what is being solved for. This is only necessary if the matrix is complex and spSEPARATED_COMPLEX_VECTORS is true. iSolution  iSolution is the imaginary portion of the vector being multiplied by the matrix. This is only necessary if the matrix is complex and spSEPARATED_COMPLEX_VECTORS is true.

spcEXTERN spREAL spNorm (  spMatrix    eMatrix )

Computes the L-infinity norm of an unfactored matrix. It is a fatal error to pass this routine a factored matrix. Returns : The largest absolute row sum of matrix. Parameters: eMatrix  Pointer to the matrix.

spcEXTERN spError spOrderAndFactor (  spMatrix    eMatrix, spREAL    RHS[], spREAL    RelThreshold, spREAL    AbsThreshold, int    DiagPivoting )

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. This is handled in a manner that is transparent to the user. The routine uses a variation of Gauss's method where the pivots are associated with L and the diagonal terms of U are one. Returns : The error code is returned. Possible errors are spNO_MEMORY, spSINGULAR and spSMALL_PIVOT. Error is cleared upon entering this function. Parameters: eMatrix  Pointer to the matrix. RHS  Representative right-hand side vector that is used to determine pivoting order when the right hand side vector is sparse. If RHS is a NULL pointer then the RHS vector is assumed to be full and it is not used when determining the pivoting order. RelThreshold  This number determines what the pivot relative threshold will be. It 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. Element growth occurs even in well-conditioned matrices. Setting the RelThreshold 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 seems to be 0.001. The default is chosen by giving a value larger than one or less than or equal to zero. This value should be increased and the matrix resolved 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. Once a valid threshold is given, it becomes the new default. The default value of RelThreshold 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. AbsThreshold  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 AbsThreshold should be set to zero. AbsThreshold 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. Once a valid threshold is given, it becomes the new default. DiagPivoting  A flag indicating that pivot selection should be confined to the diagonal if possible. If DiagPivoting 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 Sparse is efficient and well refined, while the off-diagonal 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 off-diagonal 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 off-diagonal pivoting. See also: spFactor()

spcEXTERN void spPartition (  spMatrix    eMatrix, int    Mode )

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 spFactor() to speed the factorization. When factoring a previously ordered matrix using spFactor(), Sparse 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 Mode. If Mode is set to spDIRECT_PARTITION, then the all rows are placed in the direct addressing partition. Similarly, if Mode is set to spINDIRECT_PARTITION, then the all rows are placed in the indirect addressing partition. By setting Mode to spAUTO_PARTITION, the user allows Sparse to select the partition for each row individually. spFactor() generally runs faster if Sparse 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 Sparse choose the partition. Otherwise, you should choose the partition based on the predicted density of the matrix. Parameters: eMatrix  Pointer to matrix. Mode  Mode must be one of three special codes: spDIRECT_PARTITION, spINDIRECT_PARTITION, or spAUTO_PARTITION.

spcEXTERN void spPrint (  spMatrix    eMatrix, int    PrintReordered, int    Data, int    Header )

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. Parameters: eMatrix  Pointer to matrix. PrintReordered  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 by the matrix routines. A zero indicates that the matrix should be printed as inputed, a one indicates that it should be printed reordered. Data  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 11 times as many can be printed on a row. A zero signifies that the matrix should be printed compressed. A one indicates that the matrix should be printed in all its glory. Header  Flag indicating that extra information should be given, such as row and column numbers.

spcEXTERN spREAL spPseudoCondition (  spMatrix    eMatrix )

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 RHS 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 spOrderAndFactor() or spFactor() and before it is cleared by spClear() or spInitialize(). The pseudocondition is faster to compute than the condition number calculated by spCondition(), but is not as informative. Returns : The magnitude of the ratio of the largest to smallest pivot used during previous factorization. If the matrix was singular, zero is returned. Parameters: eMatrix  Pointer to the matrix.

spcEXTERN spREAL spRoundoff (  spMatrix    eMatrix, spREAL    Rho )

This routine, along with spLargestElement(), are used to gauge the stability of a factorization. See description of spLargestElement() for more information. Returns : Returns a bound on the magnitude of the largest element in . Parameters: eMatrix  Pointer to the matrix. Rho  The bound on the magnitude of the largest element in any of the reduced submatrices. This is the number computed by the function spLargestElement() when given a factored matrix. If this number is negative, the bound will be computed automatically.

spcEXTERN void spScale (  spMatrix    eMatrix, spREAL    RHS_ScaleFactors[], spREAL    SolutionScaleFactors[] )

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 makes no sense to scale the matrix before spFactor(). If scaling is desired it should be done before spOrderAndFactor(). There are several things to take into account when choosing the scale factors. First, the scale factors are directly multiplied against 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 by 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 RHS and Solution vectors. It may be easier to simply use spOrderAndFactor() on a scaled matrix to choose the pivoting order, and then throw away the matrix. Subsequent factorizations, performed with spFactor(), will not need to have the RHS and Solution vectors descaled. Lastly, this function should not be executed before the function spMNA_Preorder(). Parameters: eMatrix  Pointer to the matrix to be scaled. SolutionScaleFactors  The array of Solution scale factors. These factors scale the columns. All scale factors are real valued. RHS_ScaleFactors  The array of RHS scale factors. These factors scale the rows. All scale factors are real valued.

spcEXTERN void spSetComplex (  spMatrix    eMatrix )

Forces matrix to be complex. Parameters: eMatrix  Pointer to matrix.

spcEXTERN void spSetReal (  spMatrix    eMatrix )

Forces matrix to be real. Parameters: eMatrix  Pointer to matrix.

spcEXTERN void spSolve (  spMatrix    eMatrix, spREAL    RHS[], spREAL    Solution[] )

Performs forward elimination and back substitution to find the unknown vector from the RHS vector and factored matrix. This routine assumes that the pivots are associated with the lower triangular matrix and that the diagonal of the upper triangular matrix consists of ones. This routine arranges the computation in different way than is traditionally used in order to exploit the sparsity of the right-hand side. See the reference in spRevision. Parameters: eMatrix  Pointer to matrix. RHS  RHS is the input data array, the right hand side. This data is undisturbed and may be reused for other solves. Solution  Solution is the output data array. This routine is constructed such that RHS and Solution can be the same array. iRHS  iRHS is the imaginary portion of the input data array, the right hand side. This data is undisturbed and may be reused for other solves. This argument is only necessary if matrix is complex and if spSEPARATED_COMPLEX_VECTOR is set true. iSolution  iSolution is the imaginary portion of the output data array. This routine is constructed such that iRHS and iSolution can be the same array. This argument is only necessary if matrix is complex and if spSEPARATED_COMPLEX_VECTOR is set true.

spcEXTERN void spSolveTransposed (  spMatrix    eMatrix, spREAL    RHS[], spREAL    Solution[] )

Performs forward elimination and back substitution to find the unknown vector from the RHS vector and transposed factored matrix. This routine is useful when performing sensitivity analysis on a circuit using the adjoint method. This routine assumes that the pivots are associated with the untransposed lower triangular matrix and that the diagonal of the untransposed upper triangular matrix consists of ones. Parameters: eMatrix  Pointer to matrix. RHS  RHS is the input data array, the right hand side. This data is undisturbed and may be reused for other solves. Solution  Solution is the output data array. This routine is constructed such that RHS and Solution can be the same array. iRHS  iRHS is the imaginary portion of the input data array, the right hand side. This data is undisturbed and may be reused for other solves. If spSEPARATED_COMPLEX_VECTOR is set false, or if matrix is real, there is no need to supply this array. iSolution  iSolution is the imaginary portion of the output data array. This routine is constructed such that iRHS and iSolution can be the same array. If spSEPARATED_COMPLEX_VECTOR is set false, or if matrix is real, there is no need to supply this array.

spcEXTERN void spStripFills (  spMatrix    eMatrix )

Strips the matrix of all fill-ins. Parameters: eMatrix  Pointer to the matrix to be stripped.

spcEXTERN void spWhereSingular (  spMatrix    eMatrix, int *    pRow, int *    pCol )

This function returns the row and column number where the matrix was detected as singular (if pivoting was allowed on the last factorization) or where a zero was detected on the diagonal (if pivoting was not allowed on the last factorization). Pivoting is performed only in spOrderAndFactor(). Parameters: eMatrix  The matrix for which the error status is desired. pRow  The row number. pCol  The column number.

---