A probabilistic approach to optimal pivoting and prediction of fill-in for random sparse matrices

Hsueh Hsieh, M. Ghausi

IEEE Transactions on Circuit Theory · 1972 · 17 citations · 13 references

Concepts

Abstract

In a previous work by the authors, a deterministic approach was used to evaluate the sparse-matrix technique for solving a large system of equation <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AX = b</tex> . In this paper, a probabilistic approach is used to further study the sparse-matrix technique. Analytic expressions for both the most probable number of fill-ins and the most probable optimal pivot for minimum fill-in in random sparse matrices has been obtained. Probabilistic prediction is also made for the fill-in, as well as the upper bound of the fill-in for randomly generated sparse matrices.

References

13