ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

In minisymposium: Tropical Algebra in Numerical Linear Algebra

Thu 10:30–11:00, Room AV 01.12
Max-plus approximation of LU factorization
James Hook (University of Bath)
Joint work with Françoise Tissuer (University of Manchester)

We present a new method for the a priori approximation of the order of magnitude of the entries in the LU factors of a matrix $A\in\mathbb{C}^{n\times n}$. We are also able to predict which permutation matrices will be chosen by partial pivoting or complete pivoting Gaussian elimination. Our method uses max-plus algebra and is based purely on the modulii of the entries in the matrix. This approximation can be used in the construction of ILU preconditioners, where the max-plus LU approximation can be used to quickly determine the positions of the largest entries in the LU factors. These positions can subsequently be used as the sparsity pattern for an ILU preconditioner.