Geodesic
Combinatorial algorithms for computing column space bases that have sparse inverses
Electronic transactions on numerical analysis, Tome 22 (2006), pp. 122-145
This paper presents a new combinatorial approach towards constructing a sparse, implicit basis for the null space of a sparse, under-determined matrix . Our approach is to compute a column space basis of

$########$

that has a sparse inverse, which could be used to represent a null space basis in implicit form. We investigate three different algorithms for computing column space bases: two greedy algorithms implemented using graph matchings, and a third, which employs a divide and conquer strategy implemented with hypergraph partitioning followed by a matching. Our results show that for many matrices from linear programming, structural analysis, and circuit simulation, it is possible to compute column space bases having sparse inverses, contrary to conventional wisdom.
Classification : 65F50, 68R10, 90C20
Keywords: sparse column space basis, sparse null space basis, block angular matrix, block diagonal matrix, matching, hypergraph partitioning, inverse of a basis 
@article{ETNA_2006__22__a2,
     author = {Pinar,  Ali and Chow,  Edmond and Pothen,  Alex},
     title = {Combinatorial algorithms for computing column space bases that have sparse inverses},
     journal = {Electronic transactions on numerical analysis},
     pages = {122--145},
     year = {2006},
     volume = {22},
     zbl = {1112.65040},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ETNA_2006__22__a2/}
}
TY  - JOUR
AU  - Pinar,  Ali
AU  - Chow,  Edmond
AU  - Pothen,  Alex
TI  - Combinatorial algorithms for computing column space bases that have sparse inverses
JO  - Electronic transactions on numerical analysis
PY  - 2006
SP  - 122
EP  - 145
VL  - 22
UR  - http://geodesic.mathdoc.fr/item/ETNA_2006__22__a2/
LA  - en
ID  - ETNA_2006__22__a2
ER  - 
%0 Journal Article
%A Pinar,  Ali
%A Chow,  Edmond
%A Pothen,  Alex
%T Combinatorial algorithms for computing column space bases that have sparse inverses
%J Electronic transactions on numerical analysis
%D 2006
%P 122-145
%V 22
%U http://geodesic.mathdoc.fr/item/ETNA_2006__22__a2/
%G en
%F ETNA_2006__22__a2
Pinar,  Ali; Chow,  Edmond; Pothen,  Alex. Combinatorial algorithms for computing column space bases that have sparse inverses. Electronic transactions on numerical analysis, Tome 22 (2006), pp. 122-145. http://geodesic.mathdoc.fr/item/ETNA_2006__22__a2/