< Back to previous page

Project

A Numerical Linear Algebra Framework for Solving Problems with Multivariate Polynomials

Multivariate polynomials are ubiquitous in engineering. Not only are they a natural modelling tool, many parameter estimation problems can alsobe written as finding the roots of a multivariate polynomial system. Most computational methods in this setting are symbolical. In fact, a whole domain of research called computer algebra sprung into being to develop and study symbolical algorithms for problems with multivariate polynomials. This has somehow prevented the growth of a numerical approach to these problems. This thesis bridges this gap to numerical methods by developing a numerical linear algebra framework that allows us to solve problems with multivariate polynomials. The two main tools in this polynomial numerical linear algebra (PLNA) framework are the singular value decomposition (SVD) and rank-revealing QR decomposition. First, we consider three basic operations on multivariate polynomials: addition, multiplication and division, and describe their corresponding operations in the PNLA framework: vector addition, vector matrix multiplication and vector decomposition along subspaces. Next, we introduce the Macaulay matrix and provide interpretations for three of its fundamental subspaces: its row space, its null space and its left null space. Orthogonal bases for these subspaces are crucial for the numerical backward stability of the algorithms and hence a recursive orthogonalization scheme is developed. Thisscheme exploits both the sparsity and structure of the Macaulay matrix.We then introduce the canonical decomposition of the vector space of multivariate polynomials. This concept will be crucial as it provides a stop criterion for many of the algorithms that are developed. Finally, we discuss 7 different applications with corresponding algorithms. These are finding a Groebner basis, computing all affine roots of a polynomial system, solving the ideal membership problem, doing the syzygy analysis, multivariate elimination, finding approximate least common multiples andgreatest common divisors and removing multiplicities of affine roots.
Date:8 Sep 2009 →  12 Sep 2013
Keywords:Bayesian networks
Disciplines:Other engineering and technology
Project type:PhD project