Nithin Govindarajan
KU Leuven, Belgium
Macaulay matrices, low-displacement rank, and the efficient computation of null-spaces
5 March 2024, 5pm
KU Leuven, Thermotechnisch Instituut
Aula van de Tweede Hoofdwet (01.02)
Abstract
Central in this talk is the so-called Macaulay matrix that arises in the problem of solving systems of polynomial equations. We discuss its algebraic properties and the computational challenges that one faces when computing its right null space. With the goal of designing asymptotically faster null space algorithms, we zoom-in on the (quasi-)Toeplitz structures of the matrix and examine how they may be exploited in computation. To this end, we review the theory of low-displacement rank matrices and particularly the Schur algorithm for Cauchy-like matrices developed by Gohberg, Kailath, and Olshevsky (GKO). We show that the GKO algorithm may be used to reduce the complexity of computing the Macaulay null space from O(dΣ6) to O(dΣ5) (where dΣ is the total degree of the polynomial equations) in the case of a (possibly overdetermined) bivariate polynomial system. This is achieved by computing a rank-revealing LU factorisation using a total pivoting strategy introduced by Ming Gu. We discuss several implementation issues to keep the algorithm fast and stable. Additionally, we also discuss extensions of the fast null space algorithm to polynomial systems expressed in the Chebyshev systems. The final part of the talk is dedicated to the challenges of extending the algorithm to systems of more than two variables. A key open problem that will be discussed is the lack-of-understanding of the displacement equation for a multi-level Toeplitz matrix and its properties under Gaussian elimination.
