Sparse User's Guide
A Sparse Linear Equation Solver
Version 1.3a
1 April 1988
Kenneth S. Kundert
Alberto Sangiovanni-Vincentelli
Department of
Electrical Engineering and Computer Sciences
University of California, Berkeley
Berkeley, Calif. 94720
June 23, 1988
1: INTRODUCTION
Sparse1.3 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 equa-
tions. 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. Sparse 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.
Sparse1.3 is generally as fast or faster than other popular sparse
matrix packages when solving many matrices of similar structure. Sparse
does not require or assume symmetry and is able to perform numerical pivot-
ing 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.
Sparse 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, Sparse is
also suitable for other uses, one in particular is solving the very large
systems of linear equations resulting from the numerical solution of par-
tial differential equations.
1.1: Features of Sparse1.3
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:
o 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.
o Ability to quickly solve the transposed system. This feature is use-
ful when computing the sensitivity of a circuit using the adjoint
method.
o 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 Sparse and the range of the integer data type, which is used to
hold matrix indices.
o 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.
o Much of the matrix initialization can be performed by Sparse,
June 23, 1988
- 2 -
providing advantages in speed and simplified coding of the calling
program.
o Ability to preorder modified node admittance matrices to enhance accu-
racy and speed.
o Ability to exploit sparsity in the right-hand side vector to reduce
unnecessary computation.
o Ability to scale matrices prior to factoring to reduce uncertainty in
the solution.
o The ability to create and build a matrix without knowing its final
size.
o The ability to add elements, and rows and columns, to a matrix after
the matrix has been reordered.
o The ability to delete rows and columns from a matrix.
o The ability to strip the fill-ins from a matrix. This can improve the
efficiency of a subsequent reordering.
o The ability to handle matrices that have rows and columns missing from
their input description.
o Ability to output the matrix in forms readable by either by people or
by the Sparse package. Basic statistics on the matrix can also be
output.
o By default all arithmetic operations and number storage use double
precision. Thus, Sparse usually gives accurate results, even on
highly ill-conditioned systems. If so desired, Sparse can be easily
configured to use single precision arithmetic.
1.2: Enhancements of Sparse1.3 over Sparse1.2
Most notable of the enhancements provided by Sparse1.3 is that it is
considerably faster on dense matrices. Also, external names have been made
unique to 7 characters and the Sparse prefix sp 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.
It is now possible for the user program to store information in the
matrix elements. It is also possible to provide a subroutine to Sparse
that uses that information to initialize the matrix. This can greatly sim-
plify the user's code.
Sparse1.3 has an FORTRAN interface. Routines written in FORTRAN can
access almost all of the features Sparse1.3.
June 23, 1988
- 3 -
1.3: Copyright Information
Sparse1.3 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 Sparse and the University of California, Berkeley are refer-
enced in all documentation for the program or product in which Sparse 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.
June 23, 1988
- 4 -
2: PRIMER
2.1: Solving Matrix Equations
Sparse contains a collection of C subprograms that can be used to
solve linear algebraic systems of equations. These systems are of the
form:
Ax = b
where A is an nxn matrix, x is the vector of n unknowns and b is the vector
of n right-hand side terms. Through out this package A is denoted Matrix,
x is denoted Solution and b is denoted RHS (for right-hand side). The sys-
tem is solved using LU factorization, so the actual solution process is
broken into two steps, the factorization or decomposition of the matrix,
performed by spFactor(), and the forward and backward substitution, per-
formed by spSolve(). spFactor() 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.
This package exploits the fact that large matrices usually are sparse
by not storing or operating on elements in the matrix that are zero. Stor-
ing 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 per-
formed by the routine spGetElement(). 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 pos-
sible to reuse the linked-list. Thus, the linked list is left in memory
and the element values are simply cleared by spClear() before the linked-
list is reused. To speed the entering of the element values into succes-
sive matrices, spGetElement() 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.
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 spOr-
derAndFactor(). Subsequent matrices of the same structure are factored
with spFactor(). 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 spOrderAndFactor() for the subsequent factor-
izations, with a noticeable speed penalty. spOrderAndFactor() monitors the
numerical stability of the factorization and will modify an existing order-
ing to maintain stability. Otherwise, an a posteriori measure of the
numerical stability of the factorization can be computed, and the matrix
reordered if necessary.
The Sparse routines allow several matrices of different structures to
June 23, 1988
- 5 -
be resident at once. When a matrix of a new structure is encountered, the
user calls spCreate(). 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 Sparse 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 spDestroy().
A more complete discussion of sparse systems of equations, methods for
solving them, their error mechanisms, and the algorithms used in Sparse can
be found in Kundert [kundert86]. A particular emphasis is placed on
matrices resulting from circuit simulators.
2.2: Error Control
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 A is
accurately factored into L and U. When ill-conditioning is a problem, the
problem as stated is probably ill-posed and the system should be reformu-
lated such that it is not so ill-conditioned. It is possible to measure
the ill-conditioning of matrix using spCondition(). This function returns
an estimate of the reciprocal of the condition number of the matrix (K(A))
[strang80]. The condition number can be used when computing a bound on the
error in the solution using the following inequality [golub83].
||dx|| (||dA|| ||db||)
------ < K(A) (------ + ------) + higher order terms
||x|| (||A|| ||b|| )
where dA and db are the uncertainties in the matrix and right-hand side
vector and are assumed small.
The second mechanism that causes uncertainty is the build up of round-
off 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 Sparse, 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 spar-
sity 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, unfor-
tunately 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 conserva-
tive value of 0.1 [duff86].
June 23, 1988
- 6 -
The growth that occurred during a factorization can be computed by
taking the ratio of the largest matrix element in any stage of the factori-
zation to the largest matrix element before factorization. The two numbers
are estimated using spLargestElement(). If the growth is found to be
excessive after spOrderAndFactor(), 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 spFactor(), the amount of growth becomes significantly
larger, then the matrix should be reconstructed and reordered using the
same relative threshold with spOrderAndFactor(). If the growth is still
excessive, then the relative threshold should be raised again.
2.3: Building the Matrix
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 ele-
ments 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 spMNA Preorder(), spFac-
tor() or spOrderAndFactor() the size of the matrix becomes fixed and may no
longer be enlarged unless the compiler option TRANSLATE is enabled.
The TRANSLATE option allows Sparse 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. Simi-
larly, 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 spDeleteRowAndCol(). Second, it allows the use of the functions
spGetElement(), spGetAdmittance(), spGetQuad(), and spGetOnes() 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.
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.
June 23, 1988
- 7 -
2.4: Initializing the Matrix
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 spClear(), which sets the value of every element in
the matrix to zero. Sparse also provides a more flexible way to clear the
matrix. Using spInitialize(), it is possible to clear and reload at least
part of the matrix in one step.
Sparse 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 spInstallIn-
itInfo() and may read it using spGetInitInfo(). The function spInitial-
ize() is a user customizable way to initialize the matrix. Passed to this
routine is a function pointer. spInitialize() sweeps through every element
in the matrix and checks the pInitInfo pointer (the user supplied pointer).
If the pInitInfo 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 pInitInfo pointer as well as the element
pointer and the external row and column numbers, allowing the user to ini-
tialize the matrix element and the right-hand side.
Why spInitialize() would be used over spClear() 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 com-
ponents contribute values to the matrix that change on every time step and
Newton iteration.
Sparse 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 resis-
tor, the capacitance of the linear capacitor, the capacitance of the non-
linear capacitor, and perhaps past values of capacitances. The user also
provides a subroutine to spInitialize() 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.
In this example, the user supplied routine might load the linear con-
ductance 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.
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 spInitialize(), resulting in a much
June 23, 1988
- 8 -
cleaner and more easily maintained simulator.
2.5: Indices
By far the most common errors made when using Sparse are related to
array indices. Sparse 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 RHS[0] corresponds to row one in the
matrix and Solution[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 Sparse 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 Sparse is coupled to programs in other languages. For exam-
ple; 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 discus-
sion, assume that ARRAY OFFSET is set so that arrays start at one in the
program that calls Sparse.
The second option that affects indices is EXPANDABLE. When EXPANDABLE
is set false the upper bound on array and matrix indices is Size, where
Size is a parameter handed to spCreate(). 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
Sparse. The upper bound on the array indices then equals the final size
determined by Sparse. This size can be determined by calling spGetSize().
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 RHS and Solution
vectors correspond to the row and column indices in the matrix. Thus, for
this example, valid data is expected in RHS at locations 2, 3, 5 and 7.
Data at other locations is ignored. Similarly, valid data is returned in
Solution 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 spGet-
Size().
June 23, 1988
- 9 -
2.6: Configuring Sparse
It is possible at compile-time to customize Sparse for your particular
application. This is done by changing the compiler options, which are kept
in the personality file, spConfig.h. There are three classes of choices
available. First are the Sparse options, which specify the dominant per-
sonality characteristics, such as if real and/or complex systems of equa-
tions are to be handled. The second class is the Sparse 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 Sparse is ported to another machine.
As an aid in the setup and testing of Sparse a test routine and
several test matrices and their solutions have been provided. The test
routine is capable of reading files generated by spFileMatrix() and
spFileVector().
By default Sparse stores all real numbers and performs all computa-
tions using double precision arithmetic. This can be changed by changing
the definition of spREAL from double to float. spREAL is defined in
spExports.h.
June 23, 1988
- 10 -
3: INTRODUCTION TO THE SPARSE ROUTINES
In this section the routines are grouped by function and briefly described.
3.1: Creating the Matrix
spCreate()
Allocates and initializes the data structure for a matrix. Necessari-
ly the first routine run for any particular matrix.
spDestroy()
Destroys the data structure for a matrix and frees the memory.
spSetReal()
spSetComplex()
These routines toggle a flag internal to Sparse that indicates that
the matrix is either real or complex. This is useful if both real and
complex matrices of identical structure are expected.
3.2: Building the Matrix
spGetElement()
Assures that the specified element exists in the matrix data structure
and returns a pointer to it.
spGetAdmittance()
spGetQuad()
spGetOnes()
These routines add a group of four related elements to the matrix.
spGetAdmittance() adds the four elements associated with a two termi-
nal admittance. spGetQuad() is a more general routine that is useful
for entering controlled sources to the matrix. spGetOnes() adds the
four structural ones to the matrix that are often encountered with
elements that do not have admittance representations.
spDeleteRowAndCol()
This function is used to delete a row and column from the matrix.
3.3: Clearing the Matrix
spClear()
Sets every element in the matrix to zero.
spInitialize()
Runs a user provided initialization routine on each element in the ma-
trix. This routine would be used in lieu of spClear().
spGetInitInfo()
spInstallInitInfo()
These routines allow the user to install and read a user-provided
pointer to initialization data for a particular matrix element.
June 23, 1988
- 11 -
spStripFills()
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.
3.4: Placing Data in the Matrix
spADD REAL ELEMENT()
spADD IMAG ELEMENT()
spADD COMPLEX ELEMENT()
Adds a value to a particular matrix element.
spADD REAL QUAD()
spADD IMAG QUAD()
spADD COMPLEX QUAD()
Adds a value to a group of four matrix elements.
3.5: Influencing the Factorization
spMNA Preorder()
This routine preorders modified node admittance matrices so that
Sparse 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.
spPartition()
Sparse partitions the matrix in an attempt to make spFactor() run as
fast as possible. The partitioning is a relatively expensive opera-
tion that is not needed in all cases. spPartition() allows the user
specify a simpler and faster partitioning.
spScale()
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.
3.6: Factoring the Matrix
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 is desired.
June 23, 1988
- 12 -
spFactor()
Factors a matrix that has already been ordered by spOrderAndFactor().
If spFactor() is passed a matrix that needs ordering, it will automat-
ically pass the matrix to spOrderAndFactor().
3.7: Solving the Matrix Equation
spSolve()
Solves the matrix equation
Ax = b
given the matrix A factored into LU form and b.
spSolveTransposed()
When working with adjoint systems, such as in sensitivity analysis, it
is desirable to quickly solve
T
A x = b
Once A has been factored into LU form, this routine can be used to
solve the transposed system without having to suffer the cost of fac-
toring the matrix again.
3.8: Numerical Error Estimation
spCondition()
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.
spNorm()
Returns the L-infinity norm (the maximum absolute row sum) of an un-
factored matrix.
spPseudoCondition()
Returns the ratio of the largest pivot to the smallest pivot of a fac-
tored matrix. This is a rough indicator of ill-conditioning in the
matrix.
spLargestElement()
If passed an unfactored matrix, this routine returns the absolute
value of the largest element in the matrix. If passed a factored ma-
trix, 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.
spRoundoff()
Returns a bound on the magnitude of the largest element in E = A-LU,
where E represents error in the matrix resulting from roundoff error
during the factorization.
June 23, 1988
- 13 -
3.9: Matrix Operations
spDeterminant()
This routine simply calculates and returns the determinant of the fac-
tored matrix.
spMultiply()
This routine multiplys the matrix by a vector on the right. This is
useful for forming the product Ax = b in order to determine if a cal-
culated solution is correct.
spMultTransposed()
Multiplys the transposed matrix by a vector on the right. This is
useful for forming the product A sup {roman T} x = b in order to
determine if a calculated solution is correct.
3.10: Matrix Statistics and Documentation
spError()
Determines the error status of a particular matrix. While most of the
Sparse routines do return an indication that an error has occurred,
some do not and so spError() provides the only way of uncovering these
errors.
spWhereSingular()
Returns the row and column number where the matrix was detected as
singular or where a zero pivot was found.
spGetSize()
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.
spElementCount()
spFillinCount()
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.
spPrint()
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 ele-
ment, whereas in the compressed format, only the existence or nonex-
istence of an element is indicated. This routine is not suitable for
use on large matrices.
June 23, 1988
- 14 -
spFileMatrix()
spFileVector()
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 Sparse. Only those elements of the matrix that are
structurally nonzero are output, so very large matrices can be sent to
a file.
spFileStats()
This routine calculates and sends some useful statistics concerning a
matrix to a file.
June 23, 1988
- 15 -
4: SPARSE ROUTINES
This section contains a complete list of the Sparse 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.
4.1: spClear()
Sets every element in the matrix to zero. The Sparse error state is
cleared to spOKAY in this routine.
void spClear( Matrix )
o Argument:
Matrix input (char *)
Pointer to matrix that is to be cleared.
June 23, 1988
- 16 -
4.2: spCondition()
spCondition() computes an estimate of the condition number using a varia-
tion 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 condi-
tioned. 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.
spREAL spCondition( Matrix, NormOfMatrix, Error )
o Returns:
An estimate of the L infinity condition number of the matrix.
o Arguments:
Matrix input (char *)
The matrix for which the condition number is desired.
NormOfMatrix input (spREAL)
The L-infinity norm of the unfactored matrix as computed by
spNorm().
Error output (int *)
Used to return the error code.
o Possible errors:
spSINGULAR
spNO MEMORY
Error is not cleared in this routine.
o Compiler options that must be set for this routine to exist:
CONDITION
June 23, 1988
- 17 -
4.3: spCreate()
Allocates and initializes the data structures associated with a matrix.
This routine is necessarily the first routine run for any particular ma-
trix.
char *spCreate( Size, Complex, Error )
o Returned:
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.
o Arguments:
Size input (int)
Size of matrix. When the compiler option EXPANDABLE is turned
on, Size is used as a lower bound on the size of the matrix.
Size must not be negative.
Complex input (int)
Type of matrix. If Complex is 0 then the matrix is real, other-
wise 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.
Error output (int *)
Returns error flag, needed because function spError() will not
work correctly if spCreate() returns NULL.
o Possible errors:
spNO MEMORY
spPANIC
June 23, 1988
- 18 -
4.4: spDeleteRowAndCol()
This function is used to delete a row and column from the matrix. The ele-
ments 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.
void spDeleteRowAndCol( Matrix, Row, Col )
o Arguments:
Matrix input (char *)
The matrix from which the row and column are to be deleted.
Row input (int)
The row to be deleted.
Col input (int)
The column to be deleted.
o Compiler options that must be set for this routine to exist:
DELETE
TRANSLATE
4.5: spDestroy()
Destroys a matrix frame and reclaims the memory.
void spDestroy( Matrix )
o Argument:
Matrix input (char *)
Pointer to the matrix frame which is to be removed from memory.
June 23, 1988
- 19 -
4.6: 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 spFactor() or spOrderAndFactor() and before spClear() or spInitial-
ize(). 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.
void spDeterminant( Matrix, Exponent, Determinant )
void spDeterminant( Matrix, Exponent, Determinant, iDeterminant )
o Arguments:
Matrix input (char *)
The matrix for which the determinant is desired.
Exponent output (int *)
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 and iDeterminant.
Determinant output (spREAL *)
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.
iDeterminant output (spREAL *)
The imaginary portion of the determinant. When the matrix is
real this pointer need not be supplied; nothing will be returned.
o Compiler options that must be set for this routine to exist:
DETERMINANT
o Bugs:
The sign of determinant may be in error if rows and columns have been
added or deleted from matrix.
June 23, 1988
- 20 -
4.7: spElementCount()
Returns the total number of structurally nonzero elements in the matrix.
int spElementCount( Matrix )
o Returns:
The total number of structurally nonzero elements.
o Argument:
Matrix input (char *)
Pointer to the matrix.
4.8: spError()
This function returns the error status of a matrix.
int MatrixError( Matrix )
o Returned:
The error status of the given matrix.
o Argument:
Matrix input (char *)
The matrix for which the error status is desired.
o Possible errors:
spOKAY
spILL CONDITIONED
spZERO PIVOT
spSINGULAR
spNO MEMORY
spPANIC
Error is not cleared in this routine.
June 23, 1988
- 21 -
4.9: spFactor()
This routine factors the matrix into LU form and is the companion routine
to spOrderAndFactor(). Unlike spOrderAndFactor(), spFactor() cannot change
the ordering. Its utility is that it is considerably faster. The standard
way to use these two routines is to first use spOrderAndFactor() for the
initial factorization. For subsequent factorizations, spFactor() is used.
If spFactor() is called for the initial factorization of the matrix, then
it will automatically call spOrderAndFactor() with the default thresholds.
If spFactor() 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 spOr-
derAndFactor(), which can reorder the matrix and remove the offensive zero
from the diagonal.
int spFactor( Matrix )
o Returned:
The error code is returned. Possible errors are listed below.
o Argument:
Matrix input (char *)
Pointer to matrix to be factored.
o Possible errors:
spZERO PIVOT
spNO MEMORY
spSINGULAR
spILL CONDITIONED
June 23, 1988
- 22 -
4.10: spFileMatrix()
Writes matrix to file in format suitable to be read back in by the matrix
test program. Normally, spFileMatrix() should be executed before the ma-
trix is factored, otherwise matrix is output in factored form. If the ma-
trix is sent to a file without the header or data, it will be in a form
that is easily plotted by typical plotting programs.
int spFileMatrix( Matrix, File, Label, Reordered, Data, Header )
o Returns:
One is returned if routine was successful, otherwise zero is returned.
The calling function can query errno (the system global error vari-
able) as to the reason why this routine failed.
o Arguments:
Matrix input (char *)
Pointer to matrix that is to be sent to file.
File input (char *)
Name of output file.
Label input (char *)
String that is transferred to file and used as a label. String
should fit on one line and have no embedded line feeds.
Reordered input (int)
Specifies whether the matrix should be output using the original
order or in reordered form. Zero specifies original order.
Data input (int)
Indicates that the element values should be output along with the
indices for each element. Element values are not output if Data
is zero. This parameter must be nonzero if matrix is to be read
by the Sparse test program.
Header input (int)
If nonzero a header is output that includes that size of the ma-
trix and the label. This parameter must be nonzero if matrix is
to be read by the Sparse test program.
o Compiler options that must be set for this routine to exist:
DOCUMENTATION
June 23, 1988
- 23 -
4.11: 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
Sparse test program. Should be executed after the matrix is factored.
int spFileStats( Matrix, File, Label )
o Returns:
One is returned if routine was successful, otherwise zero is returned.
The calling function can query errno (the system global error vari-
able) as to the reason why this routine failed.
o Arguments:
Matrix input (char *)
Pointer to matrix for which statistics are desired.
File input (char *)
Name of output file.
Label input (char *)
String that is transferred to file and is used as a label. String
should fit on one line and have no embedded line feeds.
o Compiler options that must be set for this routine to exist:
DOCUMENTATION
June 23, 1988
- 24 -
4.12: spFileVector()
Appends the RHS 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 spFileVector() is run, it must
be run after spFileMatrix() and use the same file.
int spFileVector( Matrix, File, RHS )
int spFileVector( Matrix, File, RHS, iRHS )
o Returns:
One is returned if routine was successful, otherwise zero is returned.
The calling function can query errno (the system global error vari-
able) as to the reason why this routine failed.
o Arguments:
Matrix input (char *)
Pointer to matrix that corresponds to the vector to be output.
File input (char *)
Name of file where output is to be written.
RHS input (spREAL[])
The right-hand side vector. RHS contains only the real portion
of the right-hand side vector if the matrix is complex and
spSEPARATED COMPLEX VECTORS is set true.
iRHS input (spREAL[])
Right-hand side vector, imaginary portion. Not necessary if ma-
trix is real or if spSEPARATED COMPLEX VECTORS is set false.
o Compiler options that must be set for this routine to exist:
DOCUMENTATION
June 23, 1988
- 25 -
4.13: spFillinCount()
Returns the total number of fill-ins in the matrix. A fill-in is an ele-
ment that is originally structurally zero, but becomes nonzero during the
factorization.
int spFillinCount( Matrix )
o Returns:
The total number of fill-ins.
o Argument:
Matrix input (char *)
Pointer to the matrix.
June 23, 1988
- 26 -
4.14: spGetAdmittance()
Performs same function as spGetElement() except rather than one element,
all four matrix elements for a floating admittance are reserved. This rou-
tine also works if the admittance is grounded (zero is the ground node).
This function returns a group of pointers to the four elements through Tem-
plate, which is an output. They are used by the spADD QUAD() macros to
directly access matrix elements during subsequent loads of the matrix.
spGetAdmittance() arranges the pointers in Template so that the
spADD QUAD() routines add the admittance to the elements at [Node1,Node1]
and [Node2,Node2] and subtract the admittance from the elements at
[Node1,Node2] and [Node2,Node1]. This routine is only to be used before
spMNA Preorder(), spFactor() or spOrderAndFactor() unless the compiler flag
TRANSLATE is enabled.
int spGetAdmittance( Matrix, Node1, Node2, Template )
o Returned:
The error code is returned. Possible errors are listed below.
spGetAdmittance() does not clear the error state, so it is possible to
ignore the return code of each spGetAdmittance() call, and check for
errors after constructing the whole matrix by calling spError().
o Arguments:
Matrix input (char *)
Pointer to the matrix that admittance is to be installed.
Node1 input (int)
One node number for the admittance. Node1 must be in the range
[0..Size] unless either the TRANSLATE or EXPANDABLE compiler
flags are set true. In either case Node1 must not be negative.
Node2 input (int)
Other node number for the admittance. Node2 must be in the range
[0..Size] unless either the TRANSLATE or EXPANDABLE compiler
flags are set true. In either case Node2 must not be negative.
Template output (struct spTemplate *)
Collection of pointers to four elements that are later used to
directly address elements. User must supply the template, this
routine will fill it.
o Possible errors:
spNO MEMORY
Error is not cleared in this routine.
o Compiler options that must be set for this routine to exist:
QUAD ELEMENT
June 23, 1988
- 27 -
4.15: spGetElement()
Reserves an element at [Row,Col] 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
spADD ELEMENT() macros to directly access the element. This routine is
only to be used before spMNA Preorder(), spFactor() or spOrderAndFactor()
unless the compiler option TRANSLATE is set true.
spREAL *spGetElement( Matrix, Row, Col )
o Returned:
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. spGetElement() does not clear the
error state, so it is possible to ignore the return code of each
spGetElement() call, and check for errors after constructing the whole
matrix by calling spError().
o Arguments:
Matrix input (char *)
Pointer to the matrix that the element is to be added to.
Row input (int)
Row index for element. Row must be in the range [0..Size] unless
either the TRANSLATE or EXPANDABLE compiler flags are set true.
In either case Row 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.
Col input (int)
Column index for element. Col must be in the range [0..Size] un-
less either the TRANSLATE or EXPANDABLE compiler flags are set
true. In either case Col 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.
o Possible errors:
spNO MEMORY
Error is not cleared in this routine.
June 23, 1988
- 28 -
4.16: spGetInitInfo()
With the INITIALIZE compiler option enabled Sparse allows the user to keep
initialization information with each structurally nonzero matrix element.
Each element has a pointer (referred to as pInitInfo) that is set and used
by the user. This routine returns pInitInfo from a particular matrix ele-
ment.
char *spGetInitInfo( pElement )
o Returned:
The user installed pointer pInitInfo.
o Argument:
pElement input (spREAL *)
Pointer to the element to which pInitInfo is attached.
o Compiler options that must be set for this routine to exist:
INITIALIZE
June 23, 1988
- 29 -
4.17: spGetOnes()
Performs a similar function to spGetAdmittance() 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 [Pos,Eqn] and [Eqn,Pos] and negative
ones are placed at [Neg,Eqn] and [Eqn,Neg]. This function returns a group
of pointers to the four elements through Template, which is an output.
They are used by the spADD QUAD() macros to add the ones directly to the
matrix elements during subsequent loads of the matrix. This routine is
only to be used before spMNA Preorder(), spFactor() or spOrderAndFactor()
unless the compiler flag TRANSLATE is set true.
int spGetOnes( Matrix, Pos, Neg, Eqn, Template )
o Returned:
The error code is returned. Possible errors are listed below.
spGetOnes() does not clear the error state, so it is possible to ig-
nore the return code of each spGetOnes() call, and check for errors
after constructing the whole matrix by calling spError().
o Arguments:
Matrix input (char *)
Pointer to the matrix that ones are to be entered in.
Pos input (int)
Number of positive node. Must be in the range of [0..Size] un-
less either the options EXPANDABLE or TRANSLATE are used. Zero
is the ground row. In no case may Pos be less than zero.
Neg input (int)
Number of negative node. Must be in the range of [0..Size] un-
less either the options EXPANDABLE or TRANSLATE are used. Zero is
the ground row. In no case may Neg be less than zero.
Eqn input (int)
Row that contains the branch equation. Must be in the range of
[1..Size] unless either the options EXPANDABLE or TRANSLATE are
used. In no case may Eqn be less than one.
Template output (struct spTemplate *)
Collection of pointers to four elements that are later used to
directly address elements. User must supply the template, this
routine will fill it.
o Possible errors:
spNO MEMORY
Error is not cleared in this routine.
o Compiler options that must be set for this routine to exist:
QUAD ELEMENT
June 23, 1988
- 30 -
June 23, 1988
- 31 -
4.18: spGetQuad()
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() installs four elements into the matrix and returns their
pointers in the Template structure, which is an output. The pointers are
arranged in Template such that when passed to one of the spADD QUAD() mac-
ros along with an admittance, the admittance will be added to the elements
at [Row1,Col1] and [Row2,Col2] and subtracted from the elements 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 before spMNA Preorder(),
spFactor() or spOrderAndFactor() unless TRANSLATE is set true.
int spGetQuad( Matrix, Row1, Row2, Col1, Col2, Template )
o Returned:
The error code is returned. Possible errors are listed below. spGet-
Quad() does not clear the error state, so it is possible to ignore the
return code of each spGetQuad() call, and check for errors after con-
structing the whole matrix by calling spError().
o Arguments:
Matrix input (char *)
Pointer to the matrix that quad is to be entered in.
Row1 input (int)
First row index for the elements. Row1 must be in the range
[0..Size] unless either the TRANSLATE or EXPANDABLE compiler
flags are set true. In either case Row1 must not be negative.
Row2 input (int)
Second row index for the elements. Row2 must be in the range
[0..Size] unless either the TRANSLATE or EXPANDABLE compiler
flags are set true. In either case Row2 must not be negative.
Col1 input (int)
First column index for the elements. Col1 must be in the range
[0..Size] unless either the TRANSLATE or EXPANDABLE compiler
flags are set true. In either case Col1 must not be negative.
Col2 input (int)
Second column index for the elements. Col2 must be in the range
[0..Size] unless either the TRANSLATE or EXPANDABLE compiler
flags are set true. In either case Col2 must not be negative.
Template output (struct spTemplate *)
Collection of pointers to four elements that are later used to
directly address elements. User must supply the template, this
routine will fill it.
June 23, 1988
- 32 -
o Possible errors:
spNO MEMORY
Error is not cleared in this routine.
o Compiler options that must be set for this routine to exist:
QUAD ELEMENT
4.19: 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.
int spGetSize( Matrix, External )
o Returned:
The size of the matrix.
o Arguments:
Matrix input (char *)
Pointer to the matrix for which the size is desired.
External input (int)
If External is nonzero, the external size of the matrix is re-
turned, otherwise the internal size of the matrix is returned.
June 23, 1988
- 33 -
4.20: spInitialize()
spInitialize() is a user customizable way to initialize the matrix. Passed
to this routine is a function pointer. spInitialize() sweeps through every
element in the matrix and checks the pInitInfo pointer (the user supplied
pointer). If the pInitInfo 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 pInitInfo 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.
The user function (pInit()) is expected to return a nonzero integer if
there is a fatal error and zero otherwise. Upon encountering a nonzero re-
turn code, spInitialize() terminates and returns the error code.
The Sparse error state is cleared to spOKAY in this routine.
int spInitialize( Matrix, pInit )
o Returns:
The error code returned by pInit.
o Arguments:
Matrix input (char *)
Pointer to the matrix that is to be initialized.
pInit input ((*int)())
Pointer to a function that, given a pointer to an element, a
pointer to the users data structure containing initialization in-
formation for that element, and the row and column number of the
element, initializes it.
int pInit( pElement, pInitInfo, Row, Col )
o Returns:
Nonzero if fatal error, zero otherwise.
o Arguments:
pElement input (spREAL *)
The pointer to the real portion of the element. The real portion
can be accessed using either *pElement or pElement[0]. The ima-
ginary portion can be accessed using either *(pElement+1) or
pElement[1].
pInitInfo input (char *)
The user-installed pointer to the initialization data structure.
Row input (int)
The external row number of the element.
June 23, 1988
- 34 -
Col input (int)
The external column number of the element.
o Compiler options that must be set for this routine to exist:
INITIALIZE
4.21: spInstallInitInfo()
With the INITIALIZE compiler option enabled Sparse allows the user to keep
initialization information with each structurally nonzero matrix element.
Each element has a pointer (referred to as pInitInfo) that is set and used
by the user. This routine installs the pointer pInitInfo into a particular
matrix element.
void spInstallInitInfo( pElement, pInitInfo )
o Arguments:
pElement input (spREAL *)
Pointer to the element to which pInitInfo is to be attached.
pInitInfo input (char *)
The pointer pInitInfo.
o Compiler options that must be set for this routine to exist:
INITIALIZE
June 23, 1988
- 35 -
4.22: spLargestElement()
If this routine is called before the matrix is factored, it returns the ab-
solute value of the largest element in the matrix. If called after the ma-
trix 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 ade-
quate. 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 encoun-
tered after using spOrderAndFactor(), refactor using spOrderAndFactor()
with the pivot threshold increased, say to 0.1.
spREAL spLargestElement( Matrix )
o Returns:
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.
o Argument:
Matrix input (char *)
Pointer to the matrix.
o Compiler options that must be set for this routine to exist:
STABILITY
June 23, 1988
- 36 -
4.23: spMNA Preorder()
This routine massages modified node admittance matrices to improve the per-
formance of spOrderAndFactor(). 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 ad-
mittance matrices and must be executed after the matrix has been built but
before spScale(), spNorm(), spMultiply(), spFactor(), spOrderAndFactor() or
spDeleteRowAndCol() are executed. It should be executed for the initial
factorization only.
void spMNA Preorder( Matrix )
o Argument:
Matrix input (char *)
Pointer to the matrix to be preordered.
o Compiler options that must be set for this routine to exist:
MODIFIED NODAL
June 23, 1988
- 37 -
4.24: spMultiply()
Multiplies Matrix by Solution on the right to find RHS. Assumes matrix has
not been factored. This routine can be used as a test to see if solutions
are correct.
void spMultiply( Matrix, RHS, Solution )
void spMultiply( Matrix, RHS, Solution, iRHS, iSolution )
o Arguments:
Matrix input (char *)
Pointer to the matrix.
RHS output (spREAL[])
RHS is the right hand side vector. This is what is being solved
for. RHS contains only the real portion of the right-hand side
if spSEPARATED COMPLEX VECTORS is set true.
Solution input (spREAL[])
Solution is the vector being multiplied by the matrix. Solution
contains only the real portion of that vector if
spSEPARATED COMPLEX VECTORS is set true.
iRHS output (spREAL[])
iRHS is the imaginary portion of the right hand side. This is
what is being solved for. It is only necessary to supply iRHS if
the matrix is complex and spSEPARATED COMPLEX VECTORS is set
true.
iSolution input (spREAL[])
iSolution is the imaginary portion of the vector being multiplied
by the matrix. It is only necessary to supply iRHS if the matrix
is complex and spSEPARATED COMPLEX VECTORS is set true.
o Compiler options that must be set for this routine to exist:
MULTIPLICATION
June 23, 1988
- 38 -
4.25: spMultTransposed()
Multiplies transposed Matrix by Solution on the right to find RHS. Assumes
matrix has not been factored. This routine can be used as a test to see if
solutions are correct.
void spMultTransposed( Matrix, RHS, Solution )
void spMultTransposed( Matrix, RHS, Solution, iRHS, iSolution )
o Arguments:
Matrix input (char *)
Pointer to the matrix.
RHS output (spREAL[])
RHS is the right hand side vector. This is what is being solved
for. RHS contains only the real portion of the right-hand side
if spSEPARATED COMPLEX VECTORS is set true.
Solution input (spREAL[])
Solution is the vector being multiplied by the matrix. Solution
contains only the real portion of that vector if
spSEPARATED COMPLEX VECTORS is set true.
iRHS output (spREAL[])
iRHS is the imaginary portion of the right hand side. This is
what is being solved for. It is only necessary to supply iRHS if
the matrix is complex and spSEPARATED COMPLEX VECTORS is set
true.
iSolution input (spREAL[])
iSolution is the imaginary portion of the vector being multiplied
by the matrix. It is only necessary to supply iRHS if the matrix
is complex and spSEPARATED COMPLEX VECTORS is set true.
o Compiler options that must be set for this routine to exist:
MULTIPLICATION
TRANSPOSE
June 23, 1988
- 39 -
4.26: 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.
spREAL spNorm( Matrix )
o Returns:
The largest absolute row sum (the L-infinity norm) of the matrix.
o Argument:
Matrix input (char *)
Pointer to the matrix.
o Compiler options that must be set for this routine to exist:
CONDITION
4.27: spOrderAndFactor()
This routine chooses a pivot order for the matrix and factors it into LU
form. It handles both the initial factorization and subsequent factoriza-
tions when a reordering or threshold pivoting is desired. This is handled
in a manner that is transparent to the user.
int spOrderAndFactor( Matrix, RHS, Threshold, AbsoluteThreshold, DiagPivot-
ing )
o Returned:
The error code is returned. Possible errors are listed below.
o Arguments:
Matrix input (char *)
Pointer to matrix to be factored.
RHS input (spREAL[])
Representative RHS vector that is used to determine pivoting
order when the right-hand side vector is sparse. If a term in
RHS is zero, it is assumed that it will usually be zero. Con-
versely, a nonzero term in RHS indicates that the term will often
be nonzero. If RHS 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.
Threshold input (spREAL)
This is the pivot threshold, which should be between zero and
one. If it is one then the pivoting method becomes complete
June 23, 1988
- 40 -
pivoting, which is very slow and tends to fill up the matrix. If
it is set close to zero the pivoting method becomes strict Mar-
kowitz with no threshold. The pivot threshold is used to elim-
inate 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. Set-
ting 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 spOrderAndFac-
tor. 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 Threshold was choosen for use with nearly diago-
nally dominant matrices such as node- and modified-node admit-
tance 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.
AbsoluteThreshold input (spREAL)
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 rea-
sonable prediction for the lower bound on these elements, then
AbsoluteThreshold should be set to zero. AbsoluteThreshold is
used to reduce the possibility of choosing as a pivot an element
that has suffered heavy cancellation and as a result mainly con-
sists of roundoff error. Note that if AbsoluteThreshold is set
too large, it could drastically increase the time required to
factor and solve the matrix. AbsoluteThreshold should be nonne-
gative. If no element in the matrix is larger than Absolu-
teThreshold, the warning spILL CONDITIONED is returned.
DiagPivoting input (int)
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 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
June 23, 1988
- 41 -
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.
o Possible errors:
spNO MEMORY
spSINGULAR
spILL CONDITIONED
4.28: 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 spFactor() to speed the fac-
torization.
When factoring a previously ordered matrix using spFactor(), fISparse
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 ad-
dressing or indirect addressing. Direct addressing is fastest when the ma-
trix 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 address-
ing 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 fac-
tor 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. By default (i.e., if spPar-
tition() is never called), Sparse chooses the partition for each row indi-
vidually.
void spPartition( Matrix, Mode )
o Arguments:
Matrix input (char *)
Pointer to matrix to be partitioned.
Mode input (int)
Mode must be one of three special codes: spDIRECT PARTITION,
spINDIRECT PARTITION, or spAUTO PARTITION.
June 23, 1988
- 42 -
4.29: 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 peo-
ple. This routine should not be used on large matrices.
void spPrint( Matrix, PrintReordered, Data, Header )
o Arguments:
Matrix input (char *)
Pointer to matrix to be printed.
PrintReordered input (int)
Indicates whether the matrix should be printed out in its origi-
nal 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.
Data input (int)
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.
Header input (int)
A flag indicating that extra information should be printed, such
as row and column numbers.
o Compiler options that must be set for this routine to exist:
DOCUMENTATION
June 23, 1988
- 43 -
4.30: 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 im-
ply 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.
spREAL spPseudoCondition( Matrix )
o Returns:
The magnitude of the ratio of the largest to smallest pivot used dur-
ing previous factorization. If the matrix was singular, zero is re-
turned.
o Argument:
Matrix input (char *)
Pointer to matrix.
o Compiler options that must be set for this routine to exist:
PSEUDOCONDITION
June 23, 1988
- 44 -
4.31: spRoundoff()
Returns a bound on the magnitude of the largest element in E = A-LU, where
E represents error in the matrix resulting from roundoff during the factor-
ization.
spREAL spRoundoff( Matrix, Rho )
o Returns:
Returns a bound on the magnitude of the largest element in E = A-LU.
o Arguments:
Matrix input (char *)
Pointer to matrix. Matrix must be factored.
Rho input (spREAL)
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.
o Compiler options that must be set for this routine to exist:
STABILITY
June 23, 1988
- 45 -
4.32: 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 spOrderAndFactor(). 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 ma-
trix of element uncertainties is equilibrated. Third, this function multi-
plies the scale factors times the elements, so if one row tends to have un-
certainties 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 factoriza-
tions, performed with spFactor(), will not need to have the RHS and Solu-
tion vectors descaled.
void spScale( Matrix, RHS ScaleFactors, SolutionScaleFactors )
o Arguments:
Matrix input (char *)
Pointer to the matrix to be scaled.
RHS ScaleFactors input (spREAL[])
The array of RHS scale factors. These factors scale the rows.
All scale factors are real-valued.
SolutionScaleFactors input (spREAL[])
The array of Solution scale factors. These factors scale the
columns. All scale factors are real-valued.
o Compiler options that must be set for this routine to exist:
SCALING
June 23, 1988
- 46 -
4.33: 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.
void spSetComplex( Matrix )
o Argument:
Matrix input (char *)
The matrix that is to be to be complex.
4.34: 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 ma-
trix to be set real, the compiler option REAL must be set true.
void spSetReal( Matrix )
o Argument:
Matrix input (char *)
The matrix that is to be real.
June 23, 1988
- 47 -
4.35: spSolve()
Performs the forward and backward elimination to find the unknown Solution
vector from RHS and the factored matrix.
void spSolve( Matrix, RHS, Solution )
void spSolve( Matrix, RHS, Solution, iRHS, iSolution )
o Arguments:
Matrix input (char *)
Pointer to matrix.
RHS input (spREAL[])
RHS is the input data array, the right-hand side vector. RHS con-
tains only the real portion of the right-hand side vector if
spSEPARATED COMPLEX VECTORS is set true. RHS is undisturbed and
may be reused for other solves.
Solution output (spREAL[])
Solution is the output data array, the unknown vector. This rou-
tine is constructed such that RHS and Solution can be the same
array. Solution contains only the real portion of the unknown
vector if spSEPARATED COMPLEX VECTORS is set true.
iRHS input (spREAL[])
iRHS 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 ma-
trix is real or spSEPARATED COMPLEX VECTORS is set false.
iSolution output (spREAL[])
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 unnecessary if the matrix is
real or spSEPARATED COMPLEX VECTORS is set false.
June 23, 1988
- 48 -
4.36: spSolveTransposed()
Performs the forward and backward elimination to find the unknown Solution
vector from RHS and the transposed factored matrix. This routine is useful
when performing sensitivity analysis on a circuit using the adjoint method.
void spSolveTransposed( Matrix, RHS, Solution )
void spSolveTransposed( Matrix, RHS, Solution, iRHS, iSolution )
o Arguments:
Matrix input (char *)
Pointer to matrix.
RHS input (spREAL[])
RHS is the input data array, the right-hand side vector. RHS
contains only the real portion of the right-hand side vector if
spSEPARATED COMPLEX VECTORS is set true. RHS is undisturbed and
may be reused for other solves.
Solution output (spREAL[])
Solution is the output data array, the unknown vector. This rou-
tine is constructed such that RHS and Solution can be the same
array. Solution contains only the real portion of the unknown
vector if spSEPARATED COMPLEX VECTORS is set true.
iRHS input (spREAL[])
iRHS 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.
iSolution output (spREAL[])
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 parameter is unnecessary if the matrix is
real or spSEPARATED COMPLEX VECTORS is set false.
o Compiler options that must be set for this routine to exist:
TRANSPOSE
June 23, 1988
- 49 -
4.37: spStripFills()
spStripFills() 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.
void spStripFills( Matrix )
o Argument:
Matrix input (char *)
The matrix to be stripped.
o Compiler options that must be set for this routine to exist:
STRIP
4.38: spWhereSingular()
This function returns the row and column number where the matrix was
detected as singular or where a zero pivot was found.
void spWhereSingular( Matrix, Row, Col )
o Arguments:
Matrix input (char *)
Pointer to matrix.
Row output (int *)
The row number.
Row output (int *)
The column number.
June 23, 1988
- 50 -
5: MACRO FUNCTIONS
These macro functions are used to quickly enter data into the matrix using
pointers. These pointers are originally acquired by the user from
spGetElement(), spGetAdmittance(), spGetQuad(), and spGetOnes() 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.
The macros reside in the file spExports.h. To use them, this file
must be included in the file of the calling routine and that routine must
be written in C.
5.1: spADD REAL ELEMENT()
Macro function that adds a real value to an element in the matrix by a
pointer.
spADD REAL ELEMENT( pElement , Real )
o Arguments:
pElement input (spREAL *)
A pointer to the element to which Real is to be added.
Real input (spREAL)
The real value that is to be added to the element.
5.2: spADD IMAG ELEMENT()
Macro function that adds a imaginary value to an element in the matrix by a
pointer.
spADD IMAG ELEMENT( pElement , Imag )
o Arguments:
pElement input (spREAL *)
A pointer to the element to which Imag is to be added.
Imag input (spREAL)
The imaginary value that is to be added to the element.
June 23, 1988
- 51 -
5.3: spADD COMPLEX ELEMENT()
Macro function that adds a complex value to an element in the matrix by a
pointer.
spADD COMPLEX ELEMENT( pElement, Real, Imag )
o Arguments:
pElement input (spREAL *)
A pointer to the element to which Real and Imag are to be added.
Real input (spREAL)
The real value that is to be added to the element.
Imag input (spREAL)
The imaginary value that is to be added to the element.
5.4: spADD REAL QUAD()
Macro that adds a real value to the four elements specified by Template.
The value is added to the first two elements in Template, and subtracted
from the last two.
spADD REAL QUAD( Template, Real )
o Arguments:
Template input (struct spTemplate)
Data structure containing the pointers to four matrix elements.
Real input (spREAL)
Real value to be added to the elements.
June 23, 1988
- 52 -
5.5: spADD IMAG QUAD()
Macro that adds an imaginary value to the four elements specified by Tem-
plate. The value is added to the first two elements in Template, and sub-
tracted from the last two.
spADD IMAG QUAD( Template, Imag )
o Arguments:
Template input (struct spTemplate)
Data structure containing the pointers to four matrix elements.
Imag input (spREAL)
Imaginary value to be added to the elements.
5.6: spADD COMPLEX QUAD()
Macro that adds a complex value to the four elements specified by Template.
The value is added to the first two elements in Template, and subtracted
from the last two.
spADD COMPLEX QUAD( Template, Real, Imag )
o Arguments:
Template input (struct spTemplate)
Data structure containing the pointers to four matrix elements.
Real input (spREAL)
Real value to be added to the elements.
Imag input (spREAL)
Imaginary value to be added to the elements.
June 23, 1988
- 53 -
6: CONFIGURING SPARSE
Sparse 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 spConfig.h. To
configure Sparse, spConfig.h must be edited and then Sparse must be recom-
piled.
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 desir-
able. For a more detailed explanation, see Kundert [kundert86].
6.1: Sparse Options
REAL
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.
spCOMPLEX
This specifies that the routines will be complied to handle complex systems
of equations.
EXPANDABLE
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 al-
located 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.
June 23, 1988
- 54 -
TRANSLATE
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 spGetElement(), spGetAdmittance(), spGetQuad(), and spGetOnes() rou-
tines 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
RHS and Solution 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.
INITIALIZE
Causes the spInitialize(), spGetInitInfo(), and spInstallInitInfo() rou-
tines to be compiled. These routines allow the user to store and read one
pointer in each nonzero element in the matrix. spInitialize() then calls a
user specified function for each structural nonzero in the matrix, and in-
cludes this pointer as well as the external row and column numbers as argu-
ments. This allows the user to write custom matrix and right-hand side
vector initialization routines.
DIAGONAL PIVOTING
Many matrices, and in particular node- and modified-node admittance ma-
trices, 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 satisfacto-
ry pivot can be found on the diagonal, an off-diagonal pivot will be used.
If this option is disabled, Sparse does not preferentially search the diag-
onal. Because of this, Sparse 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 ele-
ments, 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.
June 23, 1988
- 55 -
ARRAY OFFSET
This determines whether arrays start at an index of zero or one. This op-
tion 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 Sparse 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 Sparse
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.
spSEPARATED COMPLEX VECTORS
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 Complex[1].Real, then comes
Complex[1].Imag, then Complex[2].Real, 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.
MODIFIED MARKOWITZ
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 can-
didates and they all have the same Markowitz product, then the tie is bro-
ken 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.
DELETE
This specifies that the spDeleteRowAndCol() routine should be compiled.
Note that for this routine to be compiled, both DELETE and TRANSLATE should
be set true.
STRIP
This specifies that the spStripFills() routine should be compiled.
June 23, 1988
- 56 -
MODIFIED NODAL
This specifies that the spMNA Preorder(), the routine that preorders modi-
fied node admittance matrices, should be compiled. This routine results in
greater speed and accuracy if used with this type of matrix.
QUAD ELEMENT
This specifies that the routines that allow four related elements to be en-
tered into the matrix at once should be compiled. The routines affected by
QUAD ELEMENT are spGetAdmittance(), spGetQuad(), and spGetOnes().
TRANSPOSE
This specifies that spSolveTranspose() and perhaps spMultTransposed(),
which operate on the matrix as if it was transposed, should be compiled.
SCALING
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
RHS and Solution vectors. It is suggested that if scaling is desired, it
only be performed when the pivot order is being chosen, which is done in
spOrderAndFactor(). This, and when the condition number of the matrix is
calculated with spCondition(), 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.
DOCUMENTATION
This specifies that routines that are used to document the matrix,
spPrint(), spFileMatrix(), spFileVector(), and spFileStats(), should be
compiled.
DETERMINANT
This specifies that the spDeterminant() routine should be complied.
STABILITY
This specifies that spLargestElement() and spRoundoff() 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 E = A-LU. If this bound is very high after applying
spOrderAndFactor(), then the pivot threshold should be raised. If the
bound increases greatly after using spFactor(), then the matrix should
probably be reordered.
June 23, 1988
- 57 -
CONDITION
This specifies that spCondition() and spNorm(), the code that computes a
good estimate of the condition number of the matrix, should be compiled.
PSEUDOCONDITION
This specifies that spPseudoCondition(), the code that computes a crude and
easily fooled indicator of the ill-conditioning in the matrix, should be
compiled.
MULTIPLICATION
This specifies that spMultiply() and perhaps spMultTransposed(), the rou-
tines that multiply an unfactored matrix by a vector, should be compiled.
FORTRAN
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.
DEBUG
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 in-
tegrated in and are running smoothly, this option should be turned off.
With DEBUG enabled, Sparse is very defensive. If a Sparse 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
Sparse is particularly picky about is calling certain functions after an
error has occurred. If an error has occurred, do not call
spMNA Preorder(), spScale(), spOrderAndFactor(), spFactor(), spSolve(), or
spSolveTransposed() until the error has been cleared by spClear() or spIni-
tialize().
6.2: Sparse Constants
These constants are used throughout the sparse matrix routines. They
should be set to suit the type of matrices being solved.
DEFAULT THRESHOLD
The threshold used if the user enters an invalid threshold. Also the
threshold used by spFactor() when calling spOrderAndFactor(). The default
threshold should not be less than or equal to zero nor larger than one.
June 23, 1988
- 58 -
DIAG PIVOTING AS DEFAULT
This indicates whether spOrderAndFactor() should use diagonal pivoting as
default. This issue only arises when spOrderAndFactor() is called from
spFactor().
SPACE FOR ELEMENTS
This number multiplied by the size of the matrix equals the number of ele-
ments for which memory is initially allocated in spCreate().
SPACE FOR FILL INS
This number multiplied by the size of the matrix equals the number of ele-
ments for which memory is initially allocated and specifically reserved for
fill-ins in spCreate().
ELEMENTS PER ALLOCATION
The number of matrix elements requested from the malloc utility on each
call to it. Setting this value greater than one reduces the amount of
overhead spent in this system call.
MINIMUM ALLOCATED SIZE
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 es-
timated size of zero. This number must not be less than one.
EXPANSION FACTOR
The minimum increase in the allocated size of the matrix when it is expand-
ed. This number must be greater than one but shouldn't be much larger than
two.
MAX MARKOWITZ TIES
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 ele-
ments 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 pos-
sibility 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.
June 23, 1988
- 59 -
TIES MULTIPLIER
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 multi-
plied 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 accept-
ing 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.
DEFAULT PARTITION
Which partition mode is used by spPartition() as default. Possibilities
include:
spDIRECT PARTITION - each row used direct addressing, best for a few
relatively dense matrices.
spINDIRECT PARTITION - each row used indirect addressing, best for a
few very sparse matrices.
spAUTO PARTITION - 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.
PRINTER WIDTH
Gives the number of characters printable in one page width. Set to 80 for
terminals and 132 for line printers.
6.3: Machine Constants
These numbers must be updated when the program is ported to a new machine.
MACHINE RESOLUTION
This is the smallest positive real double precision number e such that
1 + e = 1.
LARGEST REAL
The largest positive real number representable by a double.
SMALLEST REAL
The smallest positive real number representable by a double.
June 23, 1988
- 60 -
LARGEST SHORT INTEGER
The largest positive integer representable by a short.
LARGEST LONG INTEGER
The largest positive integer representable by a long.
June 23, 1988
- 61 -
7: EXPORTS
7.1: Error Codes
Errors are indicated with a integer error code. Macros definitions
for these error codes are set up and placed in the file spMatrix.h. They
may be imported into the users program to give readable names to the possi-
ble matrix errors. The possible error codes and there corresponding macros
are:
spOKAY - 0
No error has occurred.
spSMALL PIVOT - 1
When reordering the matrix, no element was found which satisfies the abso-
lute threshold criteria. The largest element in the matrix was chosen as
pivot. Nonfatal.
spZERO DIAG - 2
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 spOr-
derAndFactor().
spSINGULAR - 3
Fatal error. Matrix is singular, so no unique solution exists.
spNO MEMORY - 4
Fatal error. Indicates that not enough memory is available from the system
to handle the matrix.
spPANIC - 5
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.
spFATAL - 2
Not an error flag, but rather the dividing line between fatal errors and
warnings.
June 23, 1988
- 62 -
7.2: Data Structures
There is only one data structure that may need to be imported from
Sparse 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
spGetAdmittance()
spGetOnes()
spGetQuad()
spGetAdmittance(), spGetOnes(), and spGetQuad() stuff the structure which
is later used by the spADD QUAD() macros. It is also possible for the user
to collect four pointers returned by spGetElement() and stuff them into the
template. The spADD QUAD() macros add a value into Element1 and Element2
and subtract the value from Element3 and Element4. The structure is:
struct spTemplate
{ spREAL *Element1;
spREAL *Element2;
spREAL *Element3Negated;
spREAL *Element4Negated;
};
June 23, 1988
- 63 -
8: FORTRAN COMPATIBILITY
The Sparse1.3 package contains routines that interface to a calling
program written in FORTRAN. Almost every externally available Sparse1.3
routine has a counterpart defined with the same name except that the `sp'
prefix is changed to `sf'. The spADD ELEMENT() and spADD QUAD() macros are
also replaced with the sfAdd1() and sfAdd4() functions.
Any interface between two languages is going to have portibility prob-
lems, 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 spFortran.c). 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 spConfig.h). For
details on the return value and argument list of a particular interface
routine, see the file spFortran.c.
A simple example of a FORTRAN program that calls Sparse follows.
June 23, 1988
- 64 -
Example:
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
June 23, 1988
- 65 -
9: SPARSE TEST PROGRAM
The Sparse 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 UNIX graph and
plot commands.
The Sparse test program is invoked using the following syntax.
sparse [options] [file1] [file2] ...
Options:
-s Print solution only.
-r x Use x as relative threshold.
-a x Use x as absolute threshold.
-n n Print first n terms of solution vector.
-i n Repeat build/factor/solve n times for better
timing results.
-b n Use column n of matrix as right-hand side
vector.
-p Create plot files ``filename.bef'' and
``filename.aft''.
-c Use complete (as opposed to diagonal) pivot-
ing.
-x Treat real matrix as complex with imaginary
part zero.
-t Solve transposed system.
-u Print usage message.
The presence of certain options is dependent on whether the appropriate
Sparse option has been enabled.
If no input files are specified, sparse 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 real or complex keywords. After the
header is an arbitrary number of lines that describe the structural
nonzeros in the matrix. These lines have the form row column data, where
row and column are integers and data 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 row or column 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.
June 23, 1988
- 66 -
Example:
mat0 - 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
June 23, 1988
- 67 -
10: SPARSE FILES
The following is a list of the files contained in the Sparse package
and a brief description of their contents. Of the files, only spConfig.h
is expected to be modified by the user and only spMatrix.h need be imported
into the program that calls Sparse.
spAlloc.c
This file contains the routines for allocating and deallocating objects as-
sociated with the matrices, including the matrices themselves.
o User accessible functions contained in this module:
spCreate()
spDestroy()
spError()
spWhereSingular()
spGetSize()
spSetReal()
spSetComplex()
spFillinCount()
spElementCount()
spBuild.c
This file contains the routines for clearing and loading the matrix.
o User accessible functions contained in this module:
spClear()
spGetAdmittance()
spGetElement()
spGetInitInfo()
spGetOnes()
spGetQuad()
spInitialize()
spInstallInitInfo()
spConfig.h
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 Sparse package, such as the amount of memory initial-
ly allocated for each matrix and the largest real number represented by the
machine. The user is expected to modify this file to maximize the perfor-
mance of the routines with his/her matrices.
June 23, 1988
- 68 -
spDefs.h
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.
spDoc
This reference manual. spDoc contains the manual in a form that is read-
able on-line and spDoc.ms contains the manual in a form that is suitable
for input into the text formatting program troff using the -ms macros.
spFactor.c
This file contains the routines for factoring matrices into LU form.
o User accessible functions contained in this module:
spFactor()
spOrderAndFactor()
spPartition()
June 23, 1988
- 69 -
spFortran.c
This file contains the routines for interfacing Sparse1.3 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.
o User accessible functions contained in this module:
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()
June 23, 1988
- 70 -
spMatrix.h
This file contains definitions that are useful to the calling program. In
particular, this file contains error keyword definitions, some macro func-
tions 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 Sparse functions.
spOutput.c
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 Sparse test program.
o User accessible functions contained in this module:
spFileMatrix()
spFileStats()
spFileVector()
spPrint()
spRevision
The history of updates for the program. This file also includes ordering
information for the Sparse package.
spSolve.c
This module contains the forward and backward substitution routines.
o User accessible functions contained in this module:
spSolve()
spSolveTransposed()
spTest.c
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 Sparse, it is impossible to
have one test routine thoroughly exercise Sparse. Thus, emphasis is on ex-
ercising as many capabilities as is reasonable while also providing a use-
ful tool.
June 23, 1988
- 71 -
spUtil.c
This module contains various optional utility routines.
o User accessible functions contained in this module:
spCondition()
spDeleteRowAndCol()
spDeterminant()
spLargestElement()
spMNA Preorder()
spMultiply()
spMultTransposed()
spNorm()
spPseudoCondition()
spRoundoff()
spScale()
spStripFills()
Makefile
This file is used in conjunction with the UNIX program make to compile the
matrix routines and their test program.
make.com
This file is used to automatically compile Sparse under the VMS operating
system. It needs to modified slightly before being used, see the installa-
tion notes.
June 23, 1988
- 72 -
REFERENCES
[duff86] I. S. Duff, A. M. Erisman, J. K. Reid. Direct Methods for
Sparse Matrices. Oxford University Press, 1986.
[golub86] G. H. Golub, C. F. V. Van Loan. Matrix Computations. The
Johns Hopkins University Press, 1983.
[kundert86] Kenneth S. Kundert. Sparse matrix techniques. In Circuit
Analysis, Simulation and Design, Albert Ruehli (editor).
North-Holland, 1986.
[strang80] Gilbert Strang. Linear Algebra and Its Applications.
Academic Press, 1980.
Acknowledgements
We would like to acknowledge and thank the those people that contri-
buted ideas that were incorporated into Sparse. In particular, Jacob
White, Kartikeya Mayaram, Don Webber, Tom Quarles, Howard Ko and Beresford
Parlett.
June 23, 1988
Table of Contents
1: Introduction ..................................................... 1
1.1: Features of Sparse1.3 .................................. 1
1.2: Enhancements of Sparse1.3 over Sparse1.2 ............... 2
1.3: Copyright Information .................................. 3
2: Primer ........................................................... 4
2.1: Solving Matrix Equations ............................... 4
2.2: Error Control .......................................... 5
2.3: Building the Matrix .................................... 6
2.4: Initializing the Matrix ................................ 7
2.5: Indices ................................................ 8
2.6: Configuring Sparse ..................................... 9
3: Introduction to the Sparse Routines .............................. 10
3.1: Creating the Matrix .................................... 10
3.2: Building the Matrix .................................... 10
3.3: Clearing the Matrix .................................... 10
3.4: Placing Data in the Matrix ............................. 11
3.5: Influencing the Factorization .......................... 11
3.6: Factoring the Matrix ................................... 11
3.7: Solving the Matrix Equation ............................ 12
3.8: Numerical Error Estimation ............................. 12
3.9: Matrix Operations ...................................... 13
3.10: Matrix Statistics and Documentation ................... 13
4: Routines ......................................................... 15
June 23, 1988
4.1: spClear() .............................................. 15
4.2: spCondition() .......................................... 16
4.3: spCreate() ............................................. 17
4.4: spDeleteRowAndCol() .................................... 18
4.5: spDestroy() ............................................ 18
4.6: spDeterminant() ........................................ 19
4.7: spElementCount() ....................................... 20
4.8: spError() .............................................. 20
4.9: spFactor() ............................................. 21
4.10: spFileMatrix() ........................................ 22
4.11: spFileStats() ......................................... 23
4.12: spFileVector() ........................................ 24
4.13: spFillinCount() ....................................... 25
4.14: spGetAdmittance() ..................................... 26
4.15: spGetElement() ........................................ 27
4.16: spGetInitInfo() ....................................... 28
4.17: spGetOnes() ........................................... 30
4.18: spGetQuad() ........................................... 32
4.19: spGetSize() ........................................... 32
4.20: spInitialize() ........................................ 34
4.21: spInstallInitInfo() ................................... 34
4.22: spLargestElement() .................................... 35
4.23: spMNA Preorder() ...................................... 36
4.24: spMultiply() .......................................... 37
4.25: spMultTransposed() .................................... 38
4.26: spNorm() .............................................. 39
4.27: spOrderAndFactor() .................................... 39
June 23, 1988
4.28: spPartition() ......................................... 42
4.29: spPrint() ............................................. 42
4.30: spPseudoCondition() ................................... 43
4.31: spRoundoff() .......................................... 44
4.32: spScale() ............................................. 45
4.33: spSetComplex() ........................................ 46
4.34: spSetReal() ........................................... 46
4.35: spSolve() ............................................. 47
4.36: spSolveTransposed() ................................... 48
4.37: spStripFills() ........................................ 49
4.38: spWhereSingular() ..................................... 49
5: Macro Functions .................................................. 50
5.1: spADD REAL ELEMENT() ................................... 50
5.2: spADD IMAG ELEMENT() ................................... 50
5.3: spADD COMPLEX ELEMENT() ................................ 51
5.4: spADD REAL QUAD() ...................................... 51
5.5: spADD IMAG QUAD() ...................................... 52
5.6: spADD COMPLEX QUAD() ................................... 52
6: Configuring Sparse ............................................... 53
6.1: Sparse Options ......................................... 53
6.2: Sparse Constants ....................................... 57
6.3: Machine Constants ...................................... 59
7: Exports .......................................................... 61
7.1: Error Codes ............................................ 61
7.2: Data Structures ........................................ 62
8: FORTRAN Compatibility ............................................ 63
9: Sparse Test Program .............................................. 65
June 23, 1988
10: Sparse Files .................................................... 67
References ........................................................... 72
June 23, 1988