An Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix

DOI10.1137/0713023zbMath0329.65024OpenAlexW2089370129MaRDI QIDQ4095771

Norman E. Gibbs, Paul K. Stockmeyer, William Poole

Publication date: 1976

Published in: SIAM Journal on Numerical Analysis (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Numerical computation of matrix norms, conditioning, scaling (65F35) Direct numerical methods for linear systems and matrix inversion (65F05) Canonical forms, reductions, classification (15A21) Algorithms in computer science (68W99)

Related Items (87)

Profile minimization problem for matrices and graphs ⋮ Remeshing for metal forming simulations?Part I: Two-dimensional quadrilateral remeshing ⋮ Metaheuristic algorithms for the bandwidth reduction of large-scale matrices ⋮ The optimization algorithms of network node relabeling for large finite elements program system ⋮ State-defect constraint pairing graph coarsening method for Karush-Kuhn-Tucker matrices arising in orthogonal collocation methods for optimal control ⋮ Unnamed Item ⋮ EVALUATION OF AUTOMATIC DOMAIN PARTITIONING ALGORITHMS FOR PARALLEL FINITE ELEMENT ANALYSIS ⋮ Weighted graph based ordering techniques for preconditioned conjugate gradient methods ⋮ Automated mesh decomposition and concurrent finite element analysis for hypercube multiprocessor computers ⋮ Particle swarm optimization and hill climbing for the bandwidth minimization problem ⋮ Stencil reduction algorithms for the local discontinuous Galerkin method ⋮ Adapting and optimising fluidity for high-fidelity coastal modelling ⋮ Heuristics for matrix bandwidth reduction ⋮ A variable neighborhood search and simulated annealing hybrid for the profile minimization problem ⋮ Truncated envelope peconditioning technique ⋮ A new approach to minimising the frontwidth in finite element calculations ⋮ A non-nested Galerkin multi-grid method for solving linear and nonlinear solid mechanics problems ⋮ Basis of an improved hybrid node renumbering algorithm for matrix bandwidth reduction ⋮ Two improved algorithms for envelope and wavefront reduction ⋮ A parallel solver for the \(hp\)-version of finite element methods ⋮ Parallel preconditioned conjugate-gradient type algorithms for general sparsity structures ⋮ A new algorithm for finding a pseudoperipheral vertex or the endpoints of a pseudodiameter in a graph ⋮ Improvements on non-equilibrium and transport Green function techniques: the next-generation Transiesta ⋮ A Distributed-Memory Randomized Structured Multifrontal Method for Sparse Direct Solutions ⋮ A bandwidth reduction algorithm for L-shaped and Z-shaped grid structured graphs ⋮ A cache-efficient reordering method for unstructured meshes with applications to wall-resolved large-eddy simulations ⋮ Bandwidth and profile minimization ⋮ Improving Unstructured Mesh Partitions for Multiple Criteria Using Mesh Adjacencies ⋮ JASMIN-based Two-dimensional Adaptive Combined Preconditioner for Radiation Diffusion Equations in Inertial Fusion Research ⋮ Finite element nodal ordering algorithms ⋮ Parallel block tridiagonalization of real symmetric matrices ⋮ GRASP and path relinking for the matrix bandwidth minimization. ⋮ A novel GPU-parallelized meshless method for solving compressible turbulent flows ⋮ A domain renumbering algorithm for multi-domain boundary face method ⋮ An efficient algorithm for kriging approximation and optimization with large-scale sampling data. ⋮ An improved three-dimensional implicit discrete velocity method on unstructured meshes for all Knudsen number flows ⋮ Implicit method for the solution of supersonic and hypersonic 3D flow problems with lower-upper symmetric-Gauss-Seidel preconditioner on multiple graphics processing units ⋮ Block SSOR preconditionings for high-order 3D FE systems. II: Incomplete BSSOR preconditionings ⋮ An adaptive meshing automatic scheme based on the strain energy density function ⋮ Factorization of saddle-point matrices in dynamical systems optimization -- reusing pivots ⋮ Reordering and incomplete preconditioning in serial and parallel adaptive mesh refinement and coarsening flow solutions ⋮ Bandwidth of graphs resulting from the edge clique covering problem ⋮ A branch and bound algorithm for the matrix bandwidth minimization ⋮ A constructive bandwidth reduction algorithm -- a variant of GPS algorithm ⋮ Nodal ordering for bandwidth reduction using ant system algorithm ⋮ A Hypergraph Partitioning Model for Profile Minimization ⋮ Profile minimization on compositions of graphs ⋮ Some useful strategies for unstructured edge-based solvers on shared memory machines ⋮ An evaluation of reordering algorithms to reduce the computational cost of the incomplete Cholesky-conjugate gradient method ⋮ Unnamed Item ⋮ A dual representation simulated annealing algorithm for the bandwidth minimization problem on graphs ⋮ \(H\)-theorem for continuous- and discrete-time chemical kinetic systems and a system of nucleosynthesis equations ⋮ A general strategy on the bandwidth minimization (BM) problem ⋮ Adaptive memory programming for matrix bandwidth minimization ⋮ A survey of direct methods for sparse linear systems ⋮ A hybrid algorithm for reducing matrix bandwidth ⋮ Sparse matrix factor modification in structural reanalysis ⋮ Material point method simulations using an approximate full mass matrix inverse ⋮ Reducing the bandwidth of a sparse matrix with tabu search. ⋮ Transformational deformation models of continuous thin-walled structural elements with support elements of finite sizes: theoretical foundations, computational, and physical experiments ⋮ New crash procedures for large systems of linear constraints ⋮ An evaluation of low-cost heuristics for matrix bandwidth and profile reductions ⋮ An efficient finite element solution using a large pre-solved regular element ⋮ A linear time implementation of the reverse Cuthill-McKee algorithm ⋮ Smoothing splines using compactly supported, positive definite, radial basis functions ⋮ Analysis of Probing Techniques for Sparse Approximation and Trace Estimation of Decaying Matrix Functions ⋮ Glass cutting in a small firm ⋮ Strategies for Fitting Large, Geostatistical Data in MCMC Simulation ⋮ Algorithmic optimizations of a conjugate gradient solver on shared memory architectures ⋮ Diakoptics as a general approach in engineering ⋮ Numerical solution of an inverse medium scattering problem for Maxwell's equations at fixed frequency ⋮ Level-based heuristics and hill climbing for the antibandwidth maximization problem ⋮ GRASP with path relinking heuristics for the antibandwidth problem ⋮ An iterative parallel workload balancing framework for direct condensation of substructures ⋮ A parallel multi-\(p\) method ⋮ Optimal block-tridiagonalization of matrices for coherent charge transport ⋮ A review on the application of fuzzy transform in data and image compression ⋮ Projection 2 Goes Turbulent - and Fully Implicit ⋮ A two‐step approach to finite element ordering ⋮ Calculs de complexité relatifs à une méthode de dissection emboîtée ⋮ A new matrix bandwidth reduction algorithm ⋮ Unnamed Item ⋮ Algorithms for the reduction of matrix bandwidth and profile ⋮ Addressing the envelope reduction of sparse matrices using a genetic programming system ⋮ Preconditioning techniques for large linear systems: A survey ⋮ Unnamed Item ⋮ On the bandwidth of the Kneser graph

This page was built for publication: An Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix