Position symmetric sparse matrices can be represented by graphs with elements in equations corresponding to undirected edges in the graph [12,29]. The motivating applications for this research have position symmetric or position symmetric sub-matrices that are derived from power system networks that in turn, have graph representations. Ordering a symmetric sparse matrix modifies the order in which nodes are factored and is actually little more than changing the labels associated with nodes in an undirected graph; however, this simple task can drastically effect the amount of calculations involved when factoring a sparse matrix by affecting the amount of fillin. Fillin are those matrix locations with zeros as initial values that become non-zeros during factorization.
For symmetric positive definite matrices, there is much latitude in the order to perform the calculations, because there is no requirement for pivoting for numerical stability and the only effect of modifying the order of calculations might result from changes in round-off errors [29]. Diagonally dominant matrices also can be factored with little concern for pivoting, and there are many applications where time constraints are critical, so in order to speedup sparse LU factorization, pivoting is ignored. If there is no pivoting, ordering can be performed a priori and static data structures can be used for the most efficient sequential algorithm.
There is a graph-theoretical interpretation for fillin; factoring a
node is equivalent to removing the node from the graph; however, any
path through the factored node to adjacent edges must remain and must
now be explicitly listed. This phenomenon is illustrated in
figure for a segment of a graph. In this example,
the node with the least number of edges is selected for factoring, and
two of three possible new edges are created. Only two new edges are
created because there is an existing edge already connecting a pair of
nodes. Fillin causes the number of edges in the remaining nodes to
increase, often drastically increasing the number of calculations.
The amount of fillin generated when any node is factored is bounded by
the binomial coefficient of the number of edges at a node choose
2 or
where:¯There are several notable techniques to minimize fillin, with one of the commonly used techniques being minimum-degree ordering. This ordering technique is used for position symmetric matrices and attempts to minimize fillin by selecting the next node for elimination that has the lowest degree or least number of connected edges. Minimum-degree ordering is closely related to Markowitz ordering [12] --- both heuristics select the next row/column to eliminate that has the least row/column elements. The node-tearing-based ordering technique is utilized to generate block-diagonal-bordered form sparse matrices, and minimum degree ordering is used to minimize fillin locally in the mutually independent blocks and the borders. This technique is commonly referred to as multiple minimum degree ordering [13,22]. Additional detail on minimum degree-based sparse matrix ordering is presented in appendix
is the number of fillin when factoring node k.
is the number of edges at node k.
Figure: Graph Theoretical Explanation of Fillin
Modifying the ordering of a sparse matrix is simple to perform using a
permutation matrix P of all zeros and ones that simply generates
elementary row and column exchanges. Applying the permutation matrix
P to the original linear system in equation yields the
linear system
that is solved by factoring into LU factors
and
in
or the Choleski
factor
in
and then
performing forward reduction, backward substitution, and undoing the
permutation on the x vector. For LU factorization, these steps
would require the solutions of:
For Choleski factorization, simply substitute for
in equation
. Also for Choleski
factorization, as long as a symmetric positive definite matrix A
is ordered with the permutation matrix P to
, the
resultant matrix after ordering remains symmetric positive definite.