---

spFactor.c File Reference

#include <stdio.h>
#include "spConfig.h"
#include "spMatrix.h"
#include "spDefs.h"

Functions
spError	spOrderAndFactor (spMatrix eMatrix, spREAL RHS[], spREAL RelThreshold, spREAL AbsThreshold, int DiagPivoting)
spError	spFactor (spMatrix eMatrix)
void	spPartition (spMatrix eMatrix, int Mode)
void	spcCreateInternalVectors (MatrixPtr Matrix)
void	spcRowExchange (MatrixPtr Matrix, int Row1, int Row2)
void	spcColExchange (MatrixPtr Matrix, int Col1, int Col2)

---

Detailed Description

This file contains the routines to factor the matrix into LU form.

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

Author:

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

---

Function Documentation

spError spFactor (  spMatrix    eMatrix )

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

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

This routine chooses a pivot order for the matrix and factors it into LU form. It handles both the initial factorization and subsequent factorizations when a reordering is desired. This is handled in a manner that is transparent to the user. The routine uses a variation of Gauss's method where the pivots are associated with L and the diagonal terms of U are one. Returns : The error code is returned. Possible errors are spNO_MEMORY, spSINGULAR and spSMALL_PIVOT. Error is cleared upon entering this function. Parameters: eMatrix  Pointer to the matrix. RHS  Representative right-hand side vector that is used to determine pivoting order when the right hand side vector is sparse. If RHS is a NULL pointer then the RHS vector is assumed to be full and it is not used when determining the pivoting order. RelThreshold  This number determines what the pivot relative threshold will be. It should be between zero and one. If it is one then the pivoting method becomes complete pivoting, which is very slow and tends to fill up the matrix. If it is set close to zero the pivoting method becomes strict Markowitz with no threshold. The pivot threshold is used to eliminate pivot candidates that would cause excessive element growth if they were used. Element growth is the cause of roundoff error. Element growth occurs even in well-conditioned matrices. Setting the RelThreshold large will reduce element growth and roundoff error, but setting it too large will cause execution time to be excessive and will result in a large number of fill-ins. If this occurs, accuracy can actually be degraded because of the large number of operations required on the matrix due to the large number of fill-ins. A good value seems to be 0.001. The default is chosen by giving a value larger than one or less than or equal to zero. This value should be increased and the matrix resolved if growth is found to be excessive. Changing the pivot threshold does not improve performance on matrices where growth is low, as is often the case with ill-conditioned matrices. Once a valid threshold is given, it becomes the new default. The default value of RelThreshold was choosen for use with nearly diagonally dominant matrices such as node- and modified-node admittance matrices. For these matrices it is usually best to use diagonal pivoting. For matrices without a strong diagonal, it is usually best to use a larger threshold, such as 0.01 or 0.1. AbsThreshold  The absolute magnitude an element must have to be considered as a pivot candidate, except as a last resort. This number should be set significantly smaller than the smallest diagonal element that is is expected to be placed in the matrix. If there is no reasonable prediction for the lower bound on these elements, then AbsThreshold should be set to zero. AbsThreshold is used to reduce the possibility of choosing as a pivot an element that has suffered heavy cancellation and as a result mainly consists of roundoff error. Once a valid threshold is given, it becomes the new default. DiagPivoting  A flag indicating that pivot selection should be confined to the diagonal if possible. If DiagPivoting is nonzero and if DIAGONAL_PIVOTING is enabled pivots will be chosen only from the diagonal unless there are no diagonal elements that satisfy the threshold criteria. Otherwise, the entire reduced submatrix is searched when looking for a pivot. The diagonal pivoting in Sparse is efficient and well refined, while the off-diagonal pivoting is not. For symmetric and near symmetric matrices, it is best to use diagonal pivoting because it results in the best performance when reordering the matrix and when factoring the matrix without ordering. If there is a considerable amount of nonsymmetry in the matrix, then off-diagonal pivoting may result in a better equation ordering simply because there are more pivot candidates to choose from. A better ordering results in faster subsequent factorizations. However, the initial pivot selection process takes considerably longer for off-diagonal pivoting. See also: spFactor()

void spPartition (  spMatrix    eMatrix, int    Mode )

This routine determines the cost to factor each row using both direct and indirect addressing and decides, on a row-by-row basis, which addressing mode is fastest. This information is used in spFactor() to speed the factorization. When factoring a previously ordered matrix using spFactor(), Sparse operates on a row-at-a-time basis. For speed, on each step, the row being updated is copied into a full vector and the operations are performed on that vector. This can be done one of two ways, either using direct addressing or indirect addressing. Direct addressing is fastest when the matrix is relatively dense and indirect addressing is best when the matrix is quite sparse. The user selects the type of partition used with Mode. If Mode is set to spDIRECT_PARTITION, then the all rows are placed in the direct addressing partition. Similarly, if Mode is set to spINDIRECT_PARTITION, then the all rows are placed in the indirect addressing partition. By setting Mode to spAUTO_PARTITION, the user allows Sparse to select the partition for each row individually. spFactor() generally runs faster if Sparse is allowed to choose its own partitioning, however choosing a partition is expensive. The time required to choose a partition is of the same order of the cost to factor the matrix. If you plan to factor a large number of matrices with the same structure, it is best to let Sparse choose the partition. Otherwise, you should choose the partition based on the predicted density of the matrix. Parameters: eMatrix  Pointer to matrix. Mode  Mode must be one of three special codes: spDIRECT_PARTITION, spINDIRECT_PARTITION, or spAUTO_PARTITION.

---