volume | PIER Journals

Abstract

In finite element analysis, methods for the solution of sparse linear systems of equations usually start out with reordering the coefficient matrix to reduce its bandwidth or profile. The location of pseudo-peripheral nodes is an important factor in the bandwidth and profile reduction algorithm. This paper presents a heuristic parameter, called the "width-depth ratio" and denoted by κ. With such a parameter, suitable pseudo-peripheral nodes could be found; the distance between which could be much close to or even to be the diameter of a graph compared with Gibbs-Poole-Stockmeyer (GPS) algorithm. As the new parameter was implemented in GPS algorithm, a novel bandwidth and profile reduction algorithm is proposed. Simulation results show that with the proposed algorithm bandwidth and profile could be reduced by as great as 33.33% and 11.65%, respectively, compared with the outcomes in GPS algorithm, while the execution time of both algorithms is close. Empirical results show that the proposed algorithm is superior to GPS algorithm in reducing bandwidth or profile.

1. Wang, Q., Y. C. Guo, and X. W. Shi, "An improved matrix bandwidth and profile reduction algorithm in FEM problems," PIERS Proceedings, 853-857, Hangzhou, China, March 24-28, 2008. Google Scholar

2. Wang, Q., Y. C. Guo, and X. W. Shi, "A generalized GPS algorithm for reducing the bandwidth and profile of a sparse matrix," Progress In Electromagnetics Research, Vol. 90, 121-136, 2009.
doi:10.2528/PIER09010512 Google Scholar

3. Vaish, A. and H. Parthasarathy, "Analysis of a rectangular waveguide using finite element method," Progress In Electromagnetics Research C, Vol. 2, 117-125, 2008.
doi:10.2528/PIERC08031801 Google Scholar

4. Wang, C. and T. X. Song, "Two numerical methods for calculating electromagnetic fields radiated from nature lightining," Journal of Electromagnetic Waves and Applications, No. 4, 513-528, 2005. Google Scholar

5. Hua, Y., Q. Z. Liu, Y. L. Zou, and L. Sun, "A hybrid FE-Bi method for electromagnetic scattering from dielectric bodies partially covered by conductors," Journal of Electromagnetic Waves and Applications, Vol. 22, No. 2-3, 423-430, 2008.
doi:10.1163/156939308784160802 Google Scholar

6. Cuthill, E. and J. McKee, "Reducing the bandwidth of sparse symmetric matrices," Proceedings of the 1969 24th National Conference, 157-172, 1969.
doi:10.1145/800195.805928 Google Scholar

7. Chan, W. M. and A. George, "A linear time implementation of the reverse Cuthill-McKee algorithm," BIT Numerical Mathematics, Vol. 20, No. 10, 8-14, 1980. Google Scholar

8. Gibbs, N. E., "Algorithm 509: A Hybrid profile reduction algorithm [F1]," ACM Transactions on Mathematical Software, Vol. 2, No. 4, 378-387, 1976.
doi:10.1145/355705.355713 Google Scholar

9. Gibbs, N. E., Jr. W. G. Poole, and P. K. Stockmeyer, "An algorithm for reducing the bandwidth and profile of a sparse matrix," SIAM Journal on Numerical Analysis, Vol. 13, No. 2, 236-250, 1976.
doi:10.1137/0713023 Google Scholar

10. Barnard, S. T., A. Pothen, and H. Simon, "A spectral algorithm for envelope reduction of sparse matrices," Numerical Linear Algebra with Applications, Vol. 2, No. 4, 317-334, 1995.
doi:10.1002/nla.1680020402 Google Scholar

11. Dueck, G. H. and J. Jeffs, "A heuristic bandwidth reduction algorithm," Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 18, 97-108, 1995. Google Scholar

12. Boutora, Y., N. Takorabet, R. Ibtiouen, and S. Mezani, "A new method for minimizing the bandwidth and profile of square matrices for triangular finite elements mesh," IEEE Transactions on Magnetics, Vol. 43, No. 4, 2007.
doi:10.1109/TMAG.2007.891460 Google Scholar

13. Pinana, E., I. Plana, V. Campos, and R. Marti, "GRASP and path relinking for the matrix bandwidth minimization," European Journal of Operational Research, Vol. 153, No. 1, 200-210, 2004.
doi:10.1016/S0377-2217(02)00715-4 Google Scholar

14. Rose, D. J., "A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations," Graph Theory and Computing, 183-217, 1973. Google Scholar

15. Bunchj, J., "Analysis of sparse elimination," SIAM Journal on Numerical Analysis, Vol. 11, 847-873, 1974.
doi:10.1137/0711068 Google Scholar

Dr. Qing Wang

Professor Xiao-Wei Shi