Linear-time LUP decomposition of forest-like matrices

DOI10.1016/S0898-1221(99)00124-8MaRDI QIDQ1963040zbMATH OpenOpenAlexFDO

Authors Vilmar Trevisan, David P. Jacobs

Publication date 20 January 2000

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0898-1221(99)00124-8

zbMATH Keywords

forest-like matriceslinear-time algorithmLUP decompositionmatrix decomposition

Mathematics Subject Classification ID

Factorization of matrices (15A23) Direct numerical methods for linear systems and matrix inversion (65F05)

Review text

The authors present a linear-time algorithm for finding an LUP decomposition for a square matrix \(M\), a nonsingular neighborhood matrix of a tree. It is also shown how the linear system \(Mx=b\) can be sovled in linear time.

Recommendations

• Computing the inverse of a tree's incidence matrix
• Reducing the adjacency matrix of a tree
• An Almost Linear-Time Algorithm for Graph Realization
• Efficient algorithms for solving systems of linear equations and path problems
• An O(n^ 2) simplex algorithm for a class of linear programs with tree structure

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1472121 (Why is no real title available?)
• Integer LU-factorizations
• Reducing the adjacency matrix of a tree
• The determinant of a tree's neighborhood matrix

This page was built for publication: Linear-time LUP decomposition of forest-like matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1963040)