Vol. 9
Latest Volume
All Volumes
PIERL 118 [2024] PIERL 117 [2024] PIERL 116 [2024] PIERL 115 [2024] PIERL 114 [2023] PIERL 113 [2023] PIERL 112 [2023] PIERL 111 [2023] PIERL 110 [2023] PIERL 109 [2023] PIERL 108 [2023] PIERL 107 [2022] PIERL 106 [2022] PIERL 105 [2022] PIERL 104 [2022] PIERL 103 [2022] PIERL 102 [2022] PIERL 101 [2021] PIERL 100 [2021] PIERL 99 [2021] PIERL 98 [2021] PIERL 97 [2021] PIERL 96 [2021] PIERL 95 [2021] PIERL 94 [2020] PIERL 93 [2020] PIERL 92 [2020] PIERL 91 [2020] PIERL 90 [2020] PIERL 89 [2020] PIERL 88 [2020] PIERL 87 [2019] PIERL 86 [2019] PIERL 85 [2019] PIERL 84 [2019] PIERL 83 [2019] PIERL 82 [2019] PIERL 81 [2019] PIERL 80 [2018] PIERL 79 [2018] PIERL 78 [2018] PIERL 77 [2018] PIERL 76 [2018] PIERL 75 [2018] PIERL 74 [2018] PIERL 73 [2018] PIERL 72 [2018] PIERL 71 [2017] PIERL 70 [2017] PIERL 69 [2017] PIERL 68 [2017] PIERL 67 [2017] PIERL 66 [2017] PIERL 65 [2017] PIERL 64 [2016] PIERL 63 [2016] PIERL 62 [2016] PIERL 61 [2016] PIERL 60 [2016] PIERL 59 [2016] PIERL 58 [2016] PIERL 57 [2015] PIERL 56 [2015] PIERL 55 [2015] PIERL 54 [2015] PIERL 53 [2015] PIERL 52 [2015] PIERL 51 [2015] PIERL 50 [2014] PIERL 49 [2014] PIERL 48 [2014] PIERL 47 [2014] PIERL 46 [2014] PIERL 45 [2014] PIERL 44 [2014] PIERL 43 [2013] PIERL 42 [2013] PIERL 41 [2013] PIERL 40 [2013] PIERL 39 [2013] PIERL 38 [2013] PIERL 37 [2013] PIERL 36 [2013] PIERL 35 [2012] PIERL 34 [2012] PIERL 33 [2012] PIERL 32 [2012] PIERL 31 [2012] PIERL 30 [2012] PIERL 29 [2012] PIERL 28 [2012] PIERL 27 [2011] PIERL 26 [2011] PIERL 25 [2011] PIERL 24 [2011] PIERL 23 [2011] PIERL 22 [2011] PIERL 21 [2011] PIERL 20 [2011] PIERL 19 [2010] PIERL 18 [2010] PIERL 17 [2010] PIERL 16 [2010] PIERL 15 [2010] PIERL 14 [2010] PIERL 13 [2010] PIERL 12 [2009] PIERL 11 [2009] PIERL 10 [2009] PIERL 9 [2009] PIERL 8 [2009] PIERL 7 [2009] PIERL 6 [2009] PIERL 5 [2008] PIERL 4 [2008] PIERL 3 [2008] PIERL 2 [2008] PIERL 1 [2008]
2009-06-12
An Improved Algorithm for Matrix Bandwidth and Profile Reduction in Finite Element Analysis
By
Progress In Electromagnetics Research Letters, Vol. 9, 29-38, 2009
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.
Citation
Qing Wang, and Xiao-Wei Shi, "An Improved Algorithm for Matrix Bandwidth and Profile Reduction in Finite Element Analysis," Progress In Electromagnetics Research Letters, Vol. 9, 29-38, 2009.
doi:10.2528/PIERL09042305
References

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.

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

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

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.

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

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

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.

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

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

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

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

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

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

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.

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