Block LU factorization with panel Rank Revealing Pivoting and its Communication Avoiding version

Dr Amal Khabou
Abstract
We present a block LU factorization with panel rank revealing pivoting (block LU_PRRP), an algorithm based on strong rank revealing QR for the panel factorization. Block LU_PRRP is more stable than Gaussian elimination with partial pivoting (GEPP), with a theoretical upper bound of the growth factor of $(1+ \tau b)^{(n/ b)-1}$, where $b$ is the size of the panel used during the block factorization, $\tau$ is a parameter of the strong rank revealing QR factorization, and $n$ is the number of columns of the matrix. For example, if the size of the panel is $b = 64$, and $\tau = 2$, then $(1+2b)^{(n/b)-1} = (1.079)^{n-64} \ll 2^{n-1}$, where $2^{n-1}$ is the upper bound of the growth factor of GEPP. Our extensive numerical experiments show that the new factorization scheme is as numerically stable as GEPP in practice, but it is more resistant to some pathological cases where GEPP fails. We note that the block LU_PRRP factorization does only $O(n^2 b)$ additional floating point operations compared to GEPP.
  • Computational Mathematics and Applications Seminar