DOI
10.34229/KCA2522-9664.25.2.9
UDC 517.9+519.6
1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
 eugn@ukr.net
|
|
MATRIX BANDWIDTH REDUCTION FOR INTERPOLATION
WITH SPLINES IN TENSION
Abstract. Boundary conditions widen twice a band of a matrix of a system of linear equations that arises in interpolation with splines in tension (a generalization of Briggs’ method). A node numbering scheme of the finite difference mesh that allows significantly narrow the band and reduce a profile of the matrix is proposed. The described method belongs to cognitive graphics methods and is not based on graph theory concepts. The scheme or its modifications can be extended to other similar problems.
Keywords: bandwidth reduction, profile reduction, node numbering scheme, splines in tension, Briggs’ method, banded matrix, cognitive graphics.
full text
REFERENCES
- 1. Smith W.H.F., Wessel P. Gridding with continuous curvature splines in tension. Geophysics. 1990. Vol. 55, N 3. P. 293–305.
- 2. Hadjidimos A. Successive overrelaxation (SOR) and related methods. Journal of Computational and Applied Mathematics. 2000. Vol. 123. P. 177–199.
- 3. Briggs I.C. Machine contouring using minimum curvature. Geophysics. 1974. Vol. 39, N 1. P. 39–48.
- 4. Yano M., Penn J.D., Konidaris G., Patera A.T. Draft v1.2 from Math, Numerics, & Programming (for Mechanical Engineers). September 2012. https://ocw.mit.edu/ .
- 5. Cuthill E., McKee J. Reducing the bandwidth of sparse symmetric matrices. ACM’69: Proceedings of the 1969 24th National Conference 1969. P. 157–172. https://doi.org/10.1145/ .
- 6. George A., Liu J.W.H. Computer solution of large sparse positive definite systems. Prentice Hall, 1981.
- 7. Mafteiu-Scai L.O. The bandwidths of a matrix. A survey of algorithms. Annals of West University of Timisoara — Mathematics and Computer Science. 2014. Vol. 52, Iss. 2. P. 183–223. https://doi.org/10.2478/ .
- 8. Gonzaga De Oliveira S.L., Silva L.M. Low-cost heuristics for matrix bandwidth reduction combined with a hill-climbing strategy. RAIRO — Operations Research. 2021. Vol. 55, N 4. P. 2247–2264. https://doi.org/10.1051/ .
- 9. Velikoivanenko E.A., Milenin A.S., Popov A.V., Sidoruk V.A., Khimich A.N. Methods of numerical forecasting of serviceability of welded structures on computers of hybrid architecture. Cybernetics and Systems Analysis. 2019. Vol. 55, N 1. P. 117–127. https://doi.org/10.1007/ .
- 10. Hustedt B., Operto S., Virieux J. Mixed-grid and staggered grid finite difference methods for frequency-domain acoustic wave modelling. Geophysical Journal International. 2004. Vol. 157, Iss. 3. P. 1269–1296. https://doi.org/10.1111/ .
- 11. Zhao N.Z., Fan S. Effect of choices of boundary conditions on the numerical efficiency of direct solutions of finite difference frequency domain systems with perfectly matched layers. Optics Express. 2022. Vol. 30, N 15. P. 26794–26806. https://doi.org/10.1364/ .
- 12. Програмна реалізація квазідіагональної схеми нумераціі https://github.com/yevhn/ .
- 13. GNU Octave. https://www.octave.org/ .
- 14. Nazarenko, Y. Neogene [Data set]. Zenodo. https://doi.org/10.5281/ .
- 15. Chan W.M., George A. A linear time implementation of the reverse Cuthill–McKee algorithm. BIT Numerical Mathematics. 1980. Vol. 20. P. 8–14. https://doi.org/10.1007/BF01933580 .
