Title | A fast recursive orthogonalization scheme for the Macaulay matrix |
Author(s) | Kim Batselier, Philippe Dreesen, Brian Moore |
Type | Article in Journal |
Abstract | Abstract 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. |
Keywords | Macaulay matrix, Orthogonal bases, Multivariate polynomials, Recursive orthogonalization |
ISSN | 0377-0427 |
URL |
http://www.sciencedirect.com/science/article/pii/S0377042714000636 |
Language | English |
Journal | Journal of Computational and Applied Mathematics |
Volume | 267 |
Number | 0 |
Pages | 20 - 32 |
Year | 2014 |
Edition | 0 |
Translation |
No |
Refereed |
No |