New re‐ordering algorithm for skyline method
Engineering ComputationsPublished 1 February 1985
Takeo Taniguchi, Akira Soga
Citations1
SJR quartileQ2
SJR score0.39
SNIP0.72
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
The minimum profile problem of a sparse matrix is theoretically treated, and by using the results a new profile reducer is proposed. Numerical experiments clarify that the new reducer is effective for the node re‐ordering of graphs with rather complex configuration. Further considerations on the proposed method and numerical error of the skyline method are also given.
Keywords
Computer ScienceEngineering
Reducing the bandwidth of sparse symmetric matrices
1,461 Citations1969Elizabeth Cuthill, James McKee
A direct method of obtaining an automatic nodal numbering scheme to ensure that the corresponding coefficient matrix will have a narrow bandwidth is presented.
SIAM Journal on Numerical AnalysisNested Dissection of a Regular Finite Element Mesh
1,033 Citations1973Alan D. George
This paper presents an unusual numbering of the mesh (unknowns) and shows that if the authors avoid operating on zeros, the $LDL^T $ factorization of A can be computed using the same standard algorithm in $O(n^3 )$ arithmetic operations.
Some simplified NP-complete problems
603 Citations1974M. R. Garey, D. S. Johnson +1 more
This paper shows that a number of NP-complete problems remain NP- complete even when their domains are substantially restricted, and determines essentially the lowest possible upper bounds on node degree for which the problems remainNP-complete.
SIAM Journal on Numerical AnalysisAn Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix
586 Citations1976Norman E. Gibbs, William G. Poole +1 more
Extensive testing on finite element matrices indicates that the algorithm typically produces bandwidth and profile which are comparable to those of the commonly-used reverse Cuthill–McKee algorithm, yet requires significantly less computation time.
ComputingThe NP-Completeness of the bandwidth minimization problem
407 Citations1976Ch. H. Papadimitriou
The Problem of minimizing the bandwidth of the nonzero entries of a sparse symmetric matrix by permuting its rows and columns and some related combinatorial problems are shown to be NP-Complete.
International Journal for Numerical Methods in EngineeringA comparasion of three resequencing algorithms for the reduction of matrix profile and wavefront
97 Citations1979G. C. Everstine
It is concluded that GPS is exceptionally fast, and, for the conditions under which the test was made, the algorithm best able to reduce profile and rms wavefront consistently well.
International Journal for Numerical Methods in EngineeringAutomatic reduction of frontwidth for finite element analysis
39 Citations1980Abdur Razzaque
An algorithm is presented for reducing the frontwidth of finite element meshes that takes an arbitrary input scheme and reorders the elements so as to reduce the front width.
International Journal for Numerical Methods in EngineeringAn algorithm for frontwidth reduction
26 Citations1981H. Pina
This paper presents an algorithm for obtaining a small frontwidth that is of interest when employing the frontal technique for solution of systems of linear equations in the finite element method.
Advances in Engineering Software (1978)New renumbering algorithm for minimizing the bandwidth of sparse matrices
9 Citations1980Takeo Taniguchi, Naruhito Shiraishi
The minimum bandwidth of a sparse matrix is proved to be a kind of the width of a graph which is obtained from the matrix in question, and a new renumbering algorithm which can reduce the bandwidth to the minimum or near minimum value is presented.
Journal of Structural MechanicsReducing the Bandwidth of Structural Stiffness Matrices
8 Citations1976Ichiro Konishi, Naruhito Shiraishi +1 more
A new diagrammatic procedure for reducing the bandwidth of a structural stiffness matrix is proposed through a redrawn configuration in a proposed coordinate system (with some restrictions) whose one axis corresponds to the size of the bandwidth.
Lecture notes in economics and mathematical systemsSparse Matrix Aspects of the Finite Element Method
7 Citations1976Alan D. George
Various sparse matrix techniques which have been developed to make the solution of linear algebraic equations more efficient are described and related.