next up previous
Next: Forward Reduction/Backward Substitution Up: Background Previous: Fillin

Symbolic Factorization and Static Data Structures

Sparse matrices have only a small percentage of non-zero values, consequently, they are stored in an implicit form, where only non-zero values and corresponding row and column location identifiers are stored. The most efficient sparse matrix algorithms, that do not require pivoting to maintain numerical stability, use implicit static data structures to store the matrix, in order to reduce the overhead of adding data to dynamic data structures. Static data structures require that all locations of all non-zero values be known when allocating memory for the data structures. This includes the location of all fillin. Example static data structures are the CSC or compressed storage of columns format [10,24], or C language data structures that store the non-zero values, row and column location identifiers for a specific value, , and possibly additional pointers to subsequent values in columns or rows.

A naive approach to determine fillin in a sparse matrix when performing LU factorization or Choleski factorization is to simply symbolically duplicate the operations of the factorization [12]. Such a naive algorithm would require the same time complexity as numerical factorization, , where for many sparse matrix applications [18]. However, it is possible to reduce the time complexity of symbolic factorization for set-based algorithms to less than , where represents the number of non-zero values in the factored matrix. References [9,12] each contain excellent discussions of symbolic factorization for Choleski factorization. For asymmetric matrices, if the data is diagonally dominant and there are no requirements to use pivoting or partial-pivoting to maintain numerical stability of the calculations, then an algorithm based on symmetric symbolic factorization could be implemented to determine the location of all fillin in both the upper and lower triangular portions of the matrix. If pivoting is required to maintain numerical stability when factoring a sparse matrix, non-static data structures will be required because pivoting dynamically modifies the sparsity structure of a matrix.



next up previous
Next: Forward Reduction/Backward Substitution Up: Background Previous: Fillin



David P. Koester
Sun Oct 22 16:27:33 EDT 1995