Fast implementation of the traveling-salesman-problem method for reordering columns within supernodes

DOI10.1137/20M1368070MaRDI QIDQ3382788zbMATH OpenOpenAlexFDO

Authors Mathias Jacquelin, Barry W. Peyton, 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

reordering within supernodessparse Cholesky factorizationsupernodessymbolic factorizationtraveling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• A Fast Algorithm for Reordering Sparse Matrices for Parallel Factorization
• A column approximate minimum degree ordering algorithm
• Minimal orderings revisited
• A Supernodal Approach to Sparse Partial Pivoting
• Node Selection Strategies for Bottom-Up Sparse Matrix Ordering

Cites work

• A compact row storage scheme for Cholesky factors using elimination trees
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• An Approximate Minimum Degree Ordering Algorithm
• An Efficient Algorithm to Compute Row and Column Counts for Sparse Cholesky Factorization
• Compressed Graphs and the Minimum Degree Algorithm
• Design of a multicore sparse Cholesky factorization using DAGs
• scientific article; zbMATH DE number 3816913 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 1082106 (Why is no real title available?)
• Modification of the minimum-degree algorithm by multiple elimination
• Nested Dissection of a Regular Finite Element Mesh
• On Finding Supernodes for Sparse Matrix Computations
• On the Application of the Minimum Degree Algorithm to Finite Element Systems
• Reducibility among combinatorial problems
• Reordering strategy for blocking optimization in sparse linear solvers
• The Evolution of the Minimum Degree Ordering Algorithm
• The influence of relaxed supernode partitions on the multifrontal method
• The Role of Elimination Trees in Sparse Factorization
• The University of Florida sparse matrix collection
• Three Partition Refinement Algorithms
• Triangulated graphs and the elimination process

Describes a project that uses

Uses Software

• symrcm
• SparseMatrix
• HSL_MA87

This page was built for publication: Fast implementation of the traveling-salesman-problem method for reordering columns within supernodes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3382788)