Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleA fast recursive orthogonalization scheme for the Macaulay matrix
Author(s) Kim Batselier, Philippe Dreesen, Brian Moore
TypeArticle in Journal
AbstractAbstract 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.
KeywordsMacaulay matrix, Orthogonal bases, Multivariate polynomials, Recursive orthogonalization
URL http://www.sciencedirect.com/science/article/pii/S0377042714000636
JournalJournal of Computational and Applied Mathematics
Pages20 - 32
Translation No
Refereed No