Objective 3: Implementing numerical linear algebra algorithms
We have two basic messages related to Objective 3:
- We will implement all algorithms using the basic building blocks of numerical linear algebra, so no hybrid symbolic-numerical implementations nor homotopy-based nonlinear iterative algorithms.
- We will have to master the combinatorial complexity of multivariate polynomial problems.
Challenge 1:
Rooting multivariate polynomial systems
We will develop three numerical linear algebra based algorithms for finding some or all the roots of a set of multivariate polynomials.
- Kernel based algorithm, exploiting the sparsity and quasi-Toeplitz structure via fast algorithms for recursive orthogonalization
- Columnspace (data-driven) algorithm, profiting from the duality between the rows of the null space matrix, and the columns of the quasi-Toeplitz matrix
- CS-decomposition based algorithm, eliminating variables by calculating the intersection of the row spaces of quasi-Toeplitz matrices in a particular canonical basis
Challenge 2:
A numerical linear algebra MEVP algorithm
In-depth exploration of the algebraic properties of the MEVP
- The canonical structure of a standard or generalized EVP, involving one or two matrices, is already quite complicated (the Jordan, Weierstrass and Kronecker canonical forms). As these are special cases of an MEVP, is seems quite a challenge to investigate canonical forms for the multi-parameter case, which we will attempt.
- A novel general purpose numerical linear algebra algorithm for the MEVP will be developed, either in the kernel or in the column space.
- We will maintain a public webpage with a test case repository for MEVP algorithms.
Challenge 3:
Multivariate polynomial minimization
A multivariate polynomial optimization problem has a multivariate polynomial objective function with multivariate polynomial constraints. Invoking Lagrange multipliers and zeroing all partial derivatives of the Lagrangean results in a set of multivariate polynomials, the roots of which contain all extrema.
- Shift with the objective function
By using the objective function as a multi-shift, we can evaluate the values of the objective function in the critical points as eigenvalues of a MEVP. - Calculating real minimizers
An important challenge is to verify whether the minimizing solutions (eigenvalues and vectors) are real.
Challenge 4:
Exploiting structure to tackle large scale aspects
- Exploit the sparsity and quasi-Toeplitz structures in our algorithms, as we expect to solve large-scale MEVPs
- Test our algorithms in a high-performance computing environment, with specific numerical and sparse high-performance libraries