A generalization of the fast LUP matrix decomposition algorithm and applications |
| |
Authors: | Oscar H Ibarra Shlomo Moran Roger Hui |
| |
Affiliation: | Department of Computer Science, University of Minnesota, Minneapolis, Minnesota USA;Department of Computer Science, University of Toronto, Toronto, Canada |
| |
Abstract: | We show that any m × n matrix A, over any field, can be written as a product, LSP, of three matrices, where L is a lower triangular matrix with l's on the main diagonal, S is an m × n matrix which reduces to an upper triangular matrix with nonzero diagonal elements when the zero rows are deleted, and P is an n × n permutation matrix. Moreover, L, S, and P can be found in O(mα?1n) time, where the complexity of matrix multiplication is O(mα). We use the LSP decomposition to construct fast algorithms for some important matrix problems. In particular, we develop O(mα?1n) algorithms for the following problems, where A is any m × n matrix: (1) Determine if the system of equations (where is a column vector) has a solution, and if so, find one such solution. (2) Find a generalized inverse, , of A (i.e., ). (3) Find simultaneously a maximal independent set of rows and a maximal independent set of columns of A. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|