Author:

Abstract:

One of the most pervasive tools from (numerical) linear algebra is, without any doubt, the standard eigenvalue decomposition. Eigenvalues describe the intrinsic system dynamics of many natural and scientific phenomena; they explain how a system evolves along the eigenvector direction. This makes eigenvalues and eigenvectors indispensable in a wide array of problems. More importantly, at least in the context of this dissertation, the standard eigenvalue decomposition is also essential when addressing two critical, mathematical problems: finding the common roots of a system of multivariate polynomials and computing the eigenvalues of a multiparameter eigenvalue problem. Multivariate polynomials and multiparameter eigenvalue problems offer natural tools for representing the real world through mathematical models. As a consequence, these two mathematical problems are critical in diverse fields from science and engineering, including systems theory, computational biology and chemistry, robotics, computer vision, and economics. Solving multivariate polynomial systems remains a very challenging task, in particular when dealing with high total degrees and many variables. There exist various methodologies to compute the solutions, including symbolic methods, which use Gröbner bases or resultants, and efficient numerical iterative methods like homotopy continuation, which track solution paths in continuously deformed systems. In this dissertation, the problem is approached from a (numerical) linear algebra perspective: we leverage the Macaulay matrix, a structured matrix constructed from the coefficients of the polynomials, to formulate a multidimensional realization problem within the right null space of that Macaulay matrix. This multidimensional realization problem yields standard eigenvalue problems, the eigenvalues of which correspond to the common roots of the multivariate polynomials. Although the Macaulay matrix provides an interesting (numerical) linear algebra tool for solving multivariate polynomial systems, the computation of a basis matrix for its right null space is computationally expensive and limits its application potential. This has motivated the development of a complementary column space based Macaulay matrix approach, which translates the multidimensional realization problem to the column space (avoiding the right null space). Both subspaces of the Macaulay matrix provide algorithms that find the common roots of the multivariate polynomials. Multiparameter spectral theory generalizes the classic spectral theory of linear operators to multiple linear operators linked by multiple spectral parameters. Its origins can be traced back to the problem of using separation of variables to solve boundary-value problems for partial differential equations. One way to solve such problems is via the eigenvalues of a multiparameter eigenvalue problem. Recently, it has been shown that (rectangular) multiparameter eigenvalue problem are also useful in the identification of linear time-invariant dynamical systems and model order reduction. Despite the extensive literature about one-parameter eigenvalue problems, the multiparameter case has not yet fully penetrated the general scientific community. Furthermore, the advent of rectangular multiparameter eigenvalue problems in various applications has uncovered the need for solution approaches. To fill this hiatus, this text extends the Macaulay matrix to the block Macaulay matrix, by replacing the coefficients of the polynomials with the coefficient matrices of the rectangular multiparameter eigenvalue problem. The translation of the solution approaches in the right null space and column space of the Macaulay matrix to the block Macaulay setting, resulting in some of the first (numerical) linear algebra tools for solving rectangular multiparameter eigenvalue problems, is a major contribution of this dissertation. The introduction of this block Macaulay matrix is the final piece of the puzzle to assemble a uniform block Macaulay matrix approach. Both mathematical problems-systems of multivariate polynomial equations and multiparameter eigenvalue problems-are at the heart of numerous applications. This text illustrates the critical nature of these two problems via several motivational examples from systems theory. These examples originate from the quest to find globally optimal models for single-input/single-output, linear time-invariant dynamical systems, which involves tackling multivariate polynomial optimization problems that minimize a certain polynomial cost function subject to polynomial model constraints. Tackling these motivational examples immediately demonstrates the computational challenges that come with the (block) Macaulay matrix algorithms. Therefore, this dissertation also covers the development of new techniques to exploit the structure and sparsity of the involved (block) Macaulay matrices, which enable more efficient, yet still reliable, solution methods. These techniques are combined into the MacaulayLab toolbox and are used to solve the motivational examples in a globally optimal way. Despite having its origin in a curiosity to understand the dynamical behavior of systems, this research integrates insights from various domains and provides novel solution approaches for very diverse applications, while relying on tools from numerical linear algebra.