Two improved algorithms for envelope and wavefront reduction (Q1371664)

Finite element methods in engineering lead to linear systems with large sparse symmetric matrices. Usually not all sparsity can be exploited efficiently in a Cholesky factorization or incomplete factorization for preconditioning. In particular, it is hard to take advantage of structural zeroes if they appear in a row between a structural nonzero and a diagonal element. The notions of the envelope of a matrix and of wavefronts help to clarify this discussion. The envelope and the wavefronts depend strongly on the ordering of the vertices in the grid and the optimal choice of the ordering is a graph theoretical problem. The authors describe the progress that they made and the substantial enhancement to the existing algorithms. Their results are supported by time complexity computations and by the implementation of their methods in a large number of test problems.