Algorithms for reducing the bandwidth and profile of a sparse matrix (Q4039501)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 179690
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Algorithms for reducing the bandwidth and profile of a sparse matrix |
scientific article; zbMATH DE number 179690 |
Statements
Algorithms for reducing the bandwidth and profile of a sparse matrix (English)
0 references
13 June 1993
0 references
bandwidth reduction
0 references
level structures
0 references
profile reduction
0 references
envelope reduction
0 references
algorithm
0 references
sparse symmetric matrix
0 references
NP-complete problem
0 references
0.9583411
0 references
0.93697786
0 references
0 references
0.9286571
0 references
0.91876847
0 references
0.91782224
0 references
0.90967035
0 references
The paper deals with an algorithm to reduce the bandwidth of a sparse symmetric matrix. As this is an NP-complete problem, all practical methods are of a heuristic nature. Like many such algorithms, also this one starts with a level structure on the graph associated with the matrix, and then finds two end points of a pseudo-diameter. The level sets are subsequently decomposed into connected components, which are then even further subdivided, to arrive at a new and more refined level structure. There are some examples to show the application of the procedure. Unfortunately, the algorithm is no good for reducing the profile or envelope of a matrix, which may be more important, as pure bandwidth solvers are hardly used any more.
0 references
