Predicting Structure in Sparse Matrix Computations
John R. Gilbert · SIAM Journal on Matrix Analysis and Applications · 1994
Many sparse matrix algorithms—for example, solving a sparse system of linear equations—begin by predicting the nonzero structure of the output of a matrix computation from the nonzero structure of its input. This paper is a catalog of ways to predict nonzero structure. It contains known results for some problems, including various matrix factorizations, and new results for other problems, including some eigenvector computations.