Exploiting Tropical Algebra in Numerical Linear Algebra

Join Professor Francoise Tisseur from the University of Manchester for this week's seminar.

  • Thu 1 Mar 18

    14:00 - 15:00

  • Colchester Campus

    Room 2.1

  • Event speaker

    Professor Francoise Tisseur, University of Manchester

  • Event type

    Lectures, talks and seminars
    Department of Mathematical Science Seminar Series

  • Event organiser

    Mathematical Sciences, Department of

  • Contact details

    Dr Andrew Harrison

The tropical semiring consists of the real numbers and infinity along with two binary operations, an addition defined by the max operation and a multiplication defined by the plus operation. Any semiring equipped with min or max as the addition operation is known as tropical. Tropical algebra is the tropical analogue of linear algebra, working with matrices with entries on the extended real line. The link between the usual and tropical algebras is provided by a valuation, a typical valuation for the field of complex numbers being V(x)=log|x|.

There are analogues of roots of polynomials, eigenvalues and singular values of matrices, and matrix factorizations in the tropical setting, and when combined with a valuation map these analogues offer order of magnitude approximations to roots of polynomials, eigenvalues and singular values, and factorizations of matrices in the usual algebra. What makes tropical algebra a useful tool for numerical linear algebra is that these tropical analogues are usually cheaper to compute than those in the conventional algebra. They can then be used in the design of preprocessing steps to improve the numerical behaviour of algorithms such as convergence and stability.

In this talk we concentrate on the use of tropical algebra to
(a) construct a new incomplete LU preconditioner that is usually almost as cheap to compute as the level k incomplete LU preconditioner but has properties similar to the more effective but more expensive to compute threshold incomplete LU preconditioner, and
(b) to improve the numerical stability of polynomial eigensolvers of arbitrary degree, and to design a numerically stable quadratic eigensolver.