On the performance of minimum degree and minimum local fill heuristics
in circuit simulation.
Techn. Rep., Massachusetts Institute of Technology, Dept. Chem. Eng.,
Cambridge, MA, U.S.A., Feb 1, 2001.
Data structures underlying local algorithms for obtaining
pivoting orders for sparse symmetric matrices are reviewed together
with their theoretical background.
Recently proposed heuristics as well as improvements to them are discussed
and their performance, mainly in terms of the resulting number of factorization
operations, is compared with that of the Minimum Degree and the Minimum Local
It is shown that a combination of Markowitz' algorithm with these symmetric
methods applied to the unsymmetric matrices arising in circuit simulation
yields orderings significantly better than those obtained from
Markowitz' algorithm alone, in some cases
at virtually no extra computational cost.
Impressum und Haftungsausschluß