SuiteSparseQR

Algorithm 915, SuiteSparseQR: Multifrontal multithreaded rank-revealing sparse QR factorization SuiteSparseQR is a sparse QR factorization package based on the multifrontal method. Within each frontal matrix, LAPACK and the multithreaded BLAS enable the method to obtain high performance on multicore architectures. Parallelism across different frontal matrices is handled with Intel’s Threading Building Blocks library. The symbolic analysis and ordering phase pre-eliminates singletons by permuting the input matrix A into the form [R11 R12; 0 A22] where R11 is upper triangular with diagonal entries above a given tolerance. Next, the fill-reducing ordering, column elimination tree, and frontal matrix structures are found without requiring the formation of the pattern of ATA. Approximate rank-detection is performed within each frontal matrix using Heath’s method. While Heath’s method is not always exact, it has the advantage of not requiring column pivoting and thus does not interfere with the fill-reducing ordering. For sufficiently large problems, the resulting sparse QR factorization obtains a substantial fraction of the theoretical peak performance of a multicore computer.

This software is also peer reviewed by journal TOMS.


References in zbMATH (referenced in 26 articles )

Showing results 1 to 20 of 26.
Sorted by year (citations)

1 2 next

  1. Essid, Montacer; Solomon, Justin: Quadratically regularized optimal transport on graphs (2018)
  2. Grigori, Laura; Cayrols, Sebastien; Demmel, James W.: Low rank approximation of a sparse matrix based on LU factorization with column and row tournament pivoting (2018)
  3. Gould, Nicholas; Scott, Jennifer: The state-of-the-art of preconditioners for sparse linear least-squares problems (2017)
  4. Maier, Matthias; Margetis, Dionisios; Luskin, Mitchell: Dipole excitation of surface plasmon on a conducting sheet: finite element approximation and validation (2017)
  5. Scott, Jennifer: On using Cholesky-based factorizations and regularization for solving rank-deficient sparse linear least-squares problems (2017)
  6. Sencer Nuri Yeralan; Timothy A. Davis; Wissam M. Sid-Lakhdar; Sanjay Ranka: Algorithm 980: Sparse QR Factorization on the GPU (2017)
  7. Torun, F. Sukru; Manguoglu, Murat; Aykanat, Cevdet: Parallel minimum norm solution of sparse block diagonal column overlapped underdetermined systems (2017)
  8. Agullo, Emmanuel; Buttari, Alfredo; Guermouche, Abdou; Lopez, Florent: Implementing multifrontal sparse solvers for multicore architectures with sequential task flow runtime systems (2016)
  9. Bujanović, Zvonimir; Kressner, Daniel: A block algorithm for computing antitriangular factorizations of symmetric matrices (2016)
  10. Everdij, Frank P. X.; Lloberas-Valls, Oriol; Simone, Angelo; Rixen, Daniel J.; Sluys, Lambertus J.: Domain decomposition and parallel direct solvers as an adaptive multiscale strategy for damage simulation in quasi-brittle materials (2016)
  11. Nürnberg, Robert; Sacconi, Andrea: A fitted finite element method for the numerical approximation of void electro-stress migration (2016)
  12. Arioli, Mario; Duff, Iain S.: Preconditioning linear least-squares problems by identifying a basis matrix (2015)
  13. Chandrasekaran, S.; Mhaskar, H. N.: A minimum Sobolev norm technique for the numerical discretization of PDEs (2015)
  14. Lei, Yuan: The inexact fixed matrix iteration for solving large linear inequalities in a least squares sense (2015)
  15. Morikuni, Keiichi; Hayami, Ken: Convergence of inner-iteration GMRES methods for rank-deficient least squares problems (2015)
  16. Batselier, Kim; Dreesen, Philippe; De Moor, Bart: A fast recursive orthogonalization scheme for the Macaulay matrix (2014)
  17. Goes, Fernando de; Memari, Pooran; Mullen, Patrick; Desbrun, Mathieu: Weighted triangulations for geometry processing (2014)
  18. Batselier, Kim; Dreesen, Philippe; de Moor, Bart: The geometry of multivariate polynomial division and elimination (2013)
  19. Batselier, Kim; Dreesen, Philippe; De Moor, Bart: A geometrical approach to finding multivariate approximate LCMs and GCDs (2013)
  20. Buttari, Alfredo: Fine-grained multithreading for the multifrontal $QR$ factorization of sparse matrices (2013)

1 2 next