A fast iterative orthogonalization scheme for the Macaulay matrix

In this article we present a fast recursive orthogonalization scheme for two important subspaces of the Macaulay matrix: its row space and null space. It requires a graded monomial ordering and exploits the resulting structure of the Macaulay matrix induced by this graded ordering. The resulting orthogonal basis for the row space will retain a similar structure as the Macaulay matrix and is as a consequence sparse. The computed orthogonal basis for the null space is dense but typically has smaller dimensions. Two alternative implementations for the recursive orthogonalization scheme are presented: one using the singular value decomposition and another using a sparse rank revealing multifrontal QR decomposition. Numerical experiments show the effectiveness of the proposed recursive orthogonalization scheme in both running time and required memory compared to a standard orthogonalization. The sparse multifrontal QR implementation is superior in both total run time and required memory at the cost of being slightly less reliable for determining the numerical rank. © 2014 Elsevier B.V. All rights reserved.

Publication year:2014

BOF-keylabel:yes

IOF-keylabel:yes

BOF-publication weight:1

CSS-citation score:1

Authors from:Higher Education