A generalization of the fast LUP matrix decomposition algorithm and applications

DOI10.1016/0196-6774(82)90007-4zbMath0492.65024OpenAlexW2085819076MaRDI QIDQ3954737

Shlomo Moran, Oscar H. Ibarra, Roger Hui

Publication date: 1982

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(82)90007-4

zbMATH Keywords

generalized inversematrix decomposition algorithmmatrix multiplication algorithmStrassen algorithmcomplexity of matrix multiplication

Mathematics Subject Classification ID

Factorization of matrices (15A23) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items

Fast computation of the rank profile matrix and the generalized Bruhat decomposition ⋮ Computing solutions of linear Mahler equations ⋮ On interval decomposability of \(2\)D persistence modules ⋮ The shifted number system for fast linear algebra on integer matrices ⋮ The bit complexity of matrix multiplication and of related computations in linear algebra. The segmented \(\lambda\) algorithms ⋮ Some independence results in complexity theory^† ⋮ Optimal algorithms of Gram-Schmidt type ⋮ Maximum matchings in geometric intersection graphs ⋮ Simple realizability of complete abstract topological graphs simplified ⋮ Clustered planarity testing revisited ⋮ Faster least squares approximation ⋮ Triangular \(x\)-basis decompositions and derandomization of linear algebra algorithms over \(K[x\)] ⋮ Controlling the spread of infectious diseases by using random walk method to remove many important links ⋮ High-order lifting for polynomial Sylvester matrices ⋮ Efficient algorithms for order basis computation ⋮ Unnamed Item ⋮ Rank-profile revealing Gaussian elimination and the CUP matrix decomposition ⋮ Generalized fraction-free \(LU\) factorization for singular systems with kernel extraction ⋮ Efficiently hex-meshing things with topology ⋮ Efficient decomposition of separable algebras. ⋮ A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes ⋮ Deterministic computation of the characteristic polynomial in the time of matrix multiplication ⋮ Solving structured linear systems with large displacement rank ⋮ Fast Hierarchical Solvers For Sparse Matrices Using Extended Sparsification and Low-Rank Approximation ⋮ Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation) ⋮ Generalized persistence algorithm for decomposing multiparameter persistence modules ⋮ Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm ⋮ Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules.