spdoc.txt

Delphi Pascal 数据挖掘领域算法包 稀疏线性系统分析包

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.