Fast Implementation of the Traveling-Salesman-Problem Method for Reordering Columns within Supernodes

DOI10.1137/20M1368070zbMath1477.90118OpenAlexW3197053605MaRDI QIDQ3382788

Barry W. Peyton, Mathias Jacquelin, Esmond G. Ng

Publication date: 22 September 2021

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/20m1368070

zbMATH Keywords

traveling salesman problemsparse Cholesky factorizationsupernodessymbolic factorizationreordering within supernodes

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Direct numerical methods for linear systems and matrix inversion (65F05)

Uses Software

• SparseMatrix
• symrcm
• HSL_MA87

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Triangulated graphs and the elimination process
• The university of Florida sparse matrix collection
• The Role of Elimination Trees in Sparse Factorization
• Modification of the minimum-degree algorithm by multiple elimination
• A compact row storage scheme for Cholesky factors using elimination trees
• Three Partition Refinement Algorithms
• The Evolution of the Minimum Degree Ordering Algorithm
• On Finding Supernodes for Sparse Matrix Computations
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• On the Application of the Minimum Degree Algorithm to Finite Element Systems
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• An Efficient Algorithm to Compute Row and Column Counts for Sparse Cholesky Factorization
• The influence of relaxed supernode partitions on the multifrontal method
• An Approximate Minimum Degree Ordering Algorithm
• Compressed Graphs and the Minimum Degree Algorithm
• Reducibility among Combinatorial Problems
• Design of a Multicore Sparse Cholesky Factorization Using DAGs
• Reordering Strategy for Blocking Optimization in Sparse Linear Solvers
• Nested Dissection of a Regular Finite Element Mesh