ERC Back to the Roots Seminar by Nitihin Govindarajan

Macaulay matrices, low-displacement rank, and the efficient computation of null-spaces

Start: 5/03/2024, 17:00
Location: Thermotechnisch Instituut, Aula van de Tweede Hoofdwet

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.

Everyone is welcome to attend in person.
The presentation will be streamed and can be followed by using this link: https://eu.bbcollab.com/guest/3cebcc23414f42b2b1d1cf23ab30c082

The slides and recordings of the previous seminars are available on our website.

Organized by: Bart De Moor