×

An application of the Dulmage-Mendelsohn decomposition to sparse null space bases of full row rank matrices. (English) Zbl 1258.65042

Summary: We present an efficient algorithm for computing a sparse null space basis for a full row rank matrix. We first apply the ideas of the H. M. Markowitz’s pivot selection criterion [Manage. Sci 3, 255–269 (1957; Zbl 0995.90592)] to a rank reducing algorithm to propose an efficient algorithm for computing sparse null space bases of full row rank matrices. We then describe how we can use the A. L. Dulmage and N. S. Mendelsohn [Can. J. Math. 10, 517–534 (1958; Zbl 0091.37404)] decomposition to make the resulting algorithm more efficient.

MSC:

65F30 Other matrix algorithms (MSC2010)
15A03 Vector spaces, linear dependence, rank, lineability

Software:

UMFPACK; CSparse
PDFBibTeX XMLCite
Full Text: Link