Abstract
The solution of a sparse linear system of equations is the core of the problem in many mathematical models. In this paper a strategy is proposed to reduce the bandwidth of the system matrix, so that direct banded solvers can be used with high efficiency. A combinatorial optimization method is implemented on an IBM SP2 (8 nodes) and on a Cray T3D (64 nodes) to perform a global bandwidth minimization, superior to previous constructive approaches. Examples of applications of the strategy in microwave circuit design demonstrate the efficiency of the method and its parallel implementation, as well as its versatility.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L. Tarricone, M. Dionigi, R. Sorrentino, A Strategy for the Efficient Mode-Matching Analysis of Complex Networks, Int. Journ. On MW and MM Wave C.A.E., 6, 3, (1996), pp. 183–196.
I. S. Duff, A. M. Erisman, J. K. Reid, Direct Methods for Sparse Matrices, Oxford Univ. Press, 1986.
D. Kuo, G. J. Chang, ‘The Profile Minimization Problem in Trees', SIAM J. Comput., 23, 1, (1994) 71–81.
N. E. Gibbs, W. G. Poole, P. K. Stockmeier, “An algorithm for reducing the bandwidth and profile of a sparse matrix”, SIAM J. of Numer. Anal., Vol. 13, 2, (1976) 236–250.
F. Glover, M. Laguna, ‘Tabu Search', in Modern Heuristic Techniques for Combinatorial Problems, Ed. C. Reeves, 70–150, Blackwell Sc. Publ., Oxford, 1993.
A. Beguelin, J. Dongarra, A. Geist, R. Manchek, V. Sunderam, PVM User's Guide, Oak Ridge Nat. Lab., May 1994.
R. Barriuso, A. Knies, Cray SHMEM User Library, Cray Research, 1994.
P. P. Silvester, R. L. Ferrari, Finite Elements for Electrical Engineers, Cambridge: Cambridge Univ. Press, 1990.
T. H. Hubing, M. W. Ali, G. K. Bhat, “EMAP: a 3-D finite element Modeling Code”, J. Appl. Comp. Electromagnetics Soc, vol. 8, 1, 1993.
A. Esposito, S. Fiorenzo Catalano, F. Malucelli, L. Tarricone, “Parallel heuristics for matrix bandwidth reduction problems emerging in waveguide network simulations”, AIRO 96, 17–20 Sept., Perugia, 1996
A. I. Zecevic, D.D. Sijiak, “Balanced Decomposition of Sparse Systems for Multilevel Parallel Processing”, IEEE Trans on Circ. and Syst., 41, 3, (1994), 220–233.
G. Karypis, V. Kumar, METIS: Unstructured Graph Partitioning and Sparse Matrix Ordering System, Univ. of Minnesota, 1995
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Esposito, A., Tarricone, L. (1996). Parallel heuristics for bandwidth reduction of sparse matrices with IBM SP2 and Cray T3D. In: Waśniewski, J., Dongarra, J., Madsen, K., Olesen, D. (eds) Applied Parallel Computing Industrial Computation and Optimization. PARA 1996. Lecture Notes in Computer Science, vol 1184. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-62095-8_25
Download citation
DOI: https://doi.org/10.1007/3-540-62095-8_25
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62095-2
Online ISBN: 978-3-540-49643-4
eBook Packages: Springer Book Archive