On Algorithms For Permuting Large Entries to the Diagonal of a Sparse Matrix

By Iain S. Duff, Jacko Koster. SIAM Journal on Matrix Analysis and Applications, 2000

377 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/81d3cb2f6e13ab2d627f625f3ab9ee2b8899a186

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

Citations in the corpus

Preconditioning techniques for large linear systems: a survey (2002, methodology): “These and other heuristics have been further developed and efficiently implemented in the sparse setting by Duff and Koster (Harwell Subroutine Library MC64; see [123, 124]).”
A column pre-ordering strategy for the unsymmetric-pattern multifrontal method (2004, background): “This permutation is not guaranteed to result in a zero-free diagonal, but it tends to preserve symmetry better than a complete zero-free matching [Duff 1981; Duff and Koster 2001].”
ON FAST FACTORIZATION PIVOTING METHODS FOR SPARSE SYMMETRI C INDEFINITE SYSTEMS (2006, background): “Experimental results suggest that the maximum product approach is generally the most beneficial method [6, 12, 31].”
A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling (2001, methodology): “Demmel and Li 122 have shown that, if one preprocesses the matrix using the code of Duu and Koster, static pivoting with possibly modiied diagonal values followed by iterative reenement can normally provide reasonably accurate solutions.”
A Scaling Algorithm to Equilibrate Both Rows and Columns Norms in Matrices 1 (2001, methodology): “It has given rise to several well known algorithms (see Duff, Erisman, and Reid (1986), Schneider and Zenios (1990), for instance).”
Notes on Birkhoff-von Neumann decomposition of doubly stochastic matrices (2016, background): “matching problem is polynomial time solvable, with for example MC64 [7].”
Neurobiology of Aging: Contents (2005, positive): “…increasing the diagonal dominance of the coefficient matrix; see Benzi, Haws and Tůma (2000), Haws (2002) and Haws and Meyer (2003), where the HSL MC64 preprocessing subroutines (Duff and Koster 1999, 2001) have been used in combination with various ILU and sparse approximate inverse techniques.”