What are common methods to choose pivot blocks in Block LU (for non-SPD/non-Diagonally Dominant Matrices)?


I think the best place to find for this information is in the LAPACK working notes or presentations about MAGMA's LU decomposition. See LAWN280 and LAWN282 in particular (links follow).



There's a couple of interesting strategies IMO:

  • Use the usual partial pivoting over entire panels, and only use block/tile updates on the trailing submatrix downdate. Although there's a limit to how parallel you can make this algorithm (the panel remains an unaddressed bottleneck), it has the advantage that it's basically identical to sequential partial pivoting (in accuracy and interface, all the way down to the ABI level).

  • Partial pivot over just the diagonal blocks. Cross your fingers for non-diagonally dominant matrices, but you can always statically permute the matrix prior to factorization, ie move big off-diagonal entries to within the diagonal blocks, in the hopes of them remaining large and suitable for use as a pivot at runtime. You can also combine this with thresholding/perturbation (replace a near zero pivot with something else). Since factoring a low-rank perturbation of the input gives a low rank perbutation of the desired factorization, it is likely you can recover later by using some sort of iteration (backwards refinement, or preconditioned krylov solution). This is a common strategy for sparse solvers, because they have limited pivoting choices due to fill-in and rigidity of the symbolic analysis.

  • Apply some randomized (but fast-to-apply/fast-to-invert) transform to the input matrix in an effort to make it easier to factor with limited/no pivoting. This is a bit heuristic, but is based on the practical observation that it's rare to find a random matrix where tile-pivoted (or even unpivoted) gaussian elimination fails. So transform your (bad) matrix randomly into another (hopefully better) one, factor it, then apply the inverse transformation at solve-time.

  • Mix tile-LU and panel-QR algorithms (they both work left to right), only using the latter when you detect breakdown in the tile-LU factorization. The QR steps are slower but more stable. Unfortunately tall/skinny QR of a panel is more complicated to implement in parallel, so it's quite a bit of legwork to get this algorithm off the ground.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.