Combinatorial Algorithms for Computing Column Space Bases ThatHave Sparse Inverses Page: 1 of 24
This article is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to UNT Digital Library by the UNT Libraries Government Documents Department.
Extracted Text
The following text was automatically extracted from the image on this page using optical character recognition software:
COMBINATORIAL ALGORITHMS FOR COMPUTING COLUMN
SPACE BASES THAT HAVE SPARSE INVERSES
ALI PINAR*, EDMOND CHOWt, AND ALEX POTHENT
Abstract. This paper presents a new combinatorial approach towards constructing a sparse
basis for the null space of a sparse, under-determined, full rank matrix, A. Such a null space basis
is suitable for solving solving many saddle point problems. Our approach is to form a column space
basis of A that has a sparse inverse, by selecting suitable columns of A. This basis could then be
used to form a sparse null space basis in fundamental form. We investigate three different algorithms
for computing the column space basis: two greedy approaches that rely on matching, and a third
employing a divide and conquer strategy implemented with hypergraph partitioning followed by the
greedy approach. We also discuss the complexity of selecting a column space basis when it is known
that such a basis exists in block diagonal form with a given small block size.
1. Introduction. Many applications require a basis, Z, for the null space of a
large, sparse, under-determined matrix, A. We describe new approaches for obtaining
a sparse null space basis by first computing a basis for the column space of A. The
column space basis is required to have a sparse inverse. The algorithms for computing
bases of the column space are based on the combinatorial concepts of matchings and
hypergraph partitioning.
One context in which a null space basis is required is constrained optimization
when the Karush-Kuhn-Tucker (KKT) system
(1.1) [ A T [ -ci
is solved by the null space method, also called the force method in structural me-
chanics. Here G is n x n, A is m x n with m < n, and the vectors are partitioned
to conform with G and A. For discussion purposes, we assume that A has full row
rank m. The null space method involves solving systems with the reduced-Hessian,
ZTGZ, and thus the method is often advantageous when n - m is small.
One approach for computing a null space basis, Z, is the following. Let P be a
permutation matrix such that AP can be partitioned as [B N] where B is nonsingular.
Then, a basis Z is
(1.2) Z =P[ -BlN
n-m
which embeds within the basis ann -rm-dimensional identity matrix. A basis Z of this
form is called a variable elimination basis or a fundamental null basis [19]. This basis
*Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720
(apinarelbl.gov). Supported by the Director, Office of Science, Division of Mathematical, Infor-
mation, and Computational Sciences of the U.S. Department of Energy under contract DE-AC03-
76SF00098.
tCenter for Applied Scientific Computing, Lawrence Livermore National Laboratory, L-560, Box
808, Livermore, CA 94568 (echow@llnl.gov). The work of this author was performed under the
auspices of the U.S. Department of Energy by University of California Lawrence Livermore National
Laboratory under contract No. W-7405-Eng-48.
TComputer Science Department and Center for Computational Science, Old Dominion University,
Norfolk, VA 23529 (pothen@cs. odu. edu). The work of this author was supported by NSF grant
ACI-023722, DOE grant DE-FC02-01ER25476, and Lawrence Livermore National Laboratory under
contract B542604.
1
Upcoming Pages
Here’s what’s next.
Search Inside
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Pinar, Ali; Chow, Edmond & Pothen, Alex. Combinatorial Algorithms for Computing Column Space Bases ThatHave Sparse Inverses, article, March 18, 2005; Berkeley, California. (https://digital.library.unt.edu/ark:/67531/metadc880761/m1/1/: accessed April 24, 2024), University of North Texas Libraries, UNT Digital Library, https://digital.library.unt.edu; crediting UNT Libraries Government Documents Department.