Linear-time LUP decomposition of forest-like matrices

Authors
Jacobs, DP Trevisan, V
Citation
Dp. Jacobs et V. Trevisan, Linear-time LUP decomposition of forest-like matrices, COMPUT MATH, 37(10), 1999, pp. 37-50
Citations number
5
Categorie Soggetti
Computer Science & Engineering
Journal title
COMPUTERS & MATHEMATICS WITH APPLICATIONS
ISSN journal
08981221 → ACNP
Volume
37
Issue
10
Year of publication
1999
Pages
37 - 50
Database
ISI
SICI code
0898-1221(199905)37:10<37:LLDOFM>2.0.ZU;2-2
Abstract
A square matrix M has an LUP decomposition if it can be written as LUP, whe re L is a unit lower-triangular matrix, U is an upper-triangular matrix, an d P is a permutation matrix. We present a linear-time algorithm for finding an LUP decomposition for a nonsingular neighborhood matrix of a tree. We a lso identify a more general class of matrices we call forest-like for which the algorithm can be modified. (C) 1999 Elsevier Science Ltd. All rights r eserved.