Hyperpower least squares progressive iterative approximation. (English) Zbl 1524.65176
Summary: Geometric iterative methods (GIMs) generate curves or surfaces that fit (interpolate or approximate) given sets of data points. Standard GIMs use the Richardson iteration or gradient descent method, so they converge relatively slowly. This paper investigates the GIMs acceleration method, which is based on the use of more efficient methods for the matrix inverse approximation. That is, the possibility to use hyperpower iterative methods is being explored. As a result, a novel GIM named hyperpower least squares progressive iterative approximation (HPLSPIA) is proposed. The convergence of the HPLSPIA method is analyzed, and the computational complexity is briefly discussed. The method is then applied to tensor product B-spline surface fitting. Several HPLSPIA methods utilizing different hyperpower methods for the matrix inverse approximation are experimentally compared. It is shown that polynomial factorizations used in the hyperpower iterative methods significantly affect the efficiency of the HPLSPIA methods.
MSC:
| 65F20 | Numerical solutions to overdetermined systems, pseudoinverses |
| 15A09 | Theory of matrix inversion and generalized inverses |
| 65F10 | Iterative numerical methods for linear systems |
| 65D10 | Numerical smoothing, curve fitting |
| 65D17 | Computer-aided design (modeling of curves and surfaces) |
Keywords:
geometric iterative method; hyperpower method; least squares progressive iterative approximation; surface fittingReferences:
| [1] | Lin, H.; Maekawa, T.; Deng, C., Survey on geometric iterative methods and their applications, Comput.-Aided Des., 95, 40-51 (2018) |
| [2] | Farin, G., (Curves and Surfaces for CAGD: A Practical Guide. Curves and Surfaces for CAGD: A Practical Guide, The Morgan Kaufmann Series in Computer Graphics (2002), Morgan Kaufmann) |
| [3] | Weiss, V.; Andor, L.; Renner, G.; Várady, T., Advanced surface fitting techniques, Comput. Aided Geom. Des., 19, 1, 19-42 (2002) · Zbl 0984.68166 |
| [4] | Lin, H., Local progressive-iterative approximation format for blending curves and patches, Comput. Aided Geom. Des., 27, 322-339 (2010) · Zbl 1210.65042 |
| [5] | Lin, H., Adaptive data fitting by the progressive-iterative approximation, Comput. Aided Geom. Des., 29, 463-473 (2012) · Zbl 1250.65021 |
| [6] | Lin, H.; Zhang, Z., An efficient method for fitting large data sets using T-splines, SIAM J. Sci. Comput., 35, A3052-A3068 (2013) · Zbl 1285.65008 |
| [7] | Kineri, Y.; Wang, M.; Lin, H.; Maekawa, T., \(B\)-spline surface fitting by iterative geometric interpolation/approximation algorithms, Comput.-Aided Des., 44, 697-708 (2012) |
| [8] | Lin, H.-W.; Bao, H.-J.; Wang, G.-J., Totally positive bases and progressive iteration approximation, Comput. Math. Appl., 50, 575-586 (2005) · Zbl 1084.41014 |
| [9] | Lin, H.; Zhang, Z., An extended iterative format for the progressive-iteration approximation, Comput. Graph.-UK, 35, 967-975 (2011) |
| [10] | Deng, C.; Lin, H., Progressive and iterative approximation for least squares B-spline curve and surface fitting, Comput.-Aided Des., 47, 32-44 (2014) |
| [11] | Maekawa, T.; Matsumoto, Y.; Namiki, K., Interpolation by geometric algorithm, Comput.-Aided Des., 39, 313-323 (2007) |
| [12] | Carnicer, J. M.; Delgado, J.; Peña, J., On the progressive iteration approximation property and alternative iterations, Comput. Aided Geom. Des., 28, 523-526 (2011) · Zbl 1244.65046 |
| [13] | Rios, D.; Jüttler, B., LSPIA, (stochastic) gradient descent, and parameter correction, J. Comput. Appl. Math., 406, Article 113921 pp. (2022) · Zbl 1482.65024 |
| [14] | Lin, H.; Jin, S.; Hu, Q.; Liu, Z., Constructing B-spline solids from tetrahedral meshes for isogeometric analysis, Comput. Aided Geom. Des., 35-36, 109-120 (2015) · Zbl 1417.65085 |
| [15] | Hu, C.; Ai, J.; Lin, H., Curve guided T-spline skinning for surface and solid generation, Comput. Grap., 90, 84-94 (2020) |
| [16] | Lu, L., Weighted progressive iteration approximation and convergence analysis, Comput. Aided Geom. Des., 27, 129-137 (2010) · Zbl 1210.65044 |
| [17] | Deng, C.; Ma, W., Weighted progressive interpolation of Loop subdivision surfaces, Comput.-Aided Des., 44, 424-431 (2012) |
| [18] | Liu, C.; Han, X.; Li, J., The Chebyshev accelerating method for progressive iterative approximation, Commun. Inf. Syst., 17, 25-43 (2017) · Zbl 1507.65006 |
| [19] | Liu, C.; Li, J.; Hu, L., Jacobi-PIA algorithm for bi-cubic B-spline interpolation surfaces, Graph. Model., 120, Article 101134 pp. (2022) |
| [20] | Zhang, L.; Ge, X.; Tan, J., Least square geometric iterative fitting method for generalized B-spline curves with two different kinds of weights, Vis. Comput., 32, 1109-1120 (2016) |
| [21] | Zhang, L.; Tan, J.; Ge, X.; Zheng, G., Generalized B-splines’ geometric iterative fitting method with mutually different weights, J. Comput. Appl. Math., 329, 331-343 (2018) · Zbl 1376.65014 |
| [22] | Liu, M.; Li, B.; Guo, Q.; Zhu, C.; Hu, P.; Shao, Y., Progressive iterative approximation for regularized least square bivariate B-spline surface fitting, J. Comput. Appl. Math., 327, 175-187 (2018) · Zbl 1371.41012 |
| [23] | Huang, Z.-D.; Wang, H.-D., On a progressive and iterative approximation method with memory for least square fitting, Comput. Aided Geom. Des., 82, Article 101931 pp. (2020) · Zbl 1450.65019 |
| [24] | Wang, H., On extended progressive and iterative approximation for least squares fitting, Vis. Comput., 38, 591-602 (2022) |
| [25] | Ebrahimi, A.; Loghmani, G. B., A composite iterative procedure with fast convergence rate for the progressive-iteration approximation of curves, J. Comput. Appl. Math., 359, 1-15 (2019) · Zbl 1416.65057 |
| [26] | Schulz, G., Iterative Berechung der reziproken Matrix, Z. Angew. Math. Mech., 13, 57-59 (1933) · JFM 59.0535.04 |
| [27] | Ben-Israel, A., An iterative method for computing the generalized inverse of an arbitrary matrix, Math. Comp., 19, 452-455 (1965) · Zbl 0136.12703 |
| [28] | Garnett III, J. M.; Ben-Israel, A.; Yau, S. S., A hyperpower iterative method for computing matrix products involving the generalized inverse, SIAM J. Numer. Anal., 8, 104-109 (1971) · Zbl 0217.52605 |
| [29] | Ben-Israel, A.; Greville, T. N.E., (Generalized Inverses: Theory and Applications. Generalized Inverses: Theory and Applications, CMS Books in Mathematics (2003), Springer-Verlag New York) · Zbl 1026.15004 |
| [30] | Wei, Y.; Stanimirović, P.; Petković, M., Numerical and Symbolic Computations of Generalized Inverses (2018), World Scientific · Zbl 1404.65002 |
| [31] | Soleymani, F.; Salmani, H.; Rasouli, M., Finding the Moore-Penrose inverse by a new matrix iteration, J. Appl. Math. Comput., 47, 33-48 (2015) · Zbl 1325.65058 |
| [32] | Hotelling, H., Some new methods in matrix calculation, Ann. Math. Stat., 14, 1-34 (1943) · Zbl 0061.27007 |
| [33] | Sen, S. K.; Prabhu, S. S., Optimal iterative schemes for computing the Moore-Penrose matrix inverse, Internat. J. Systems Sci., 7, 847-852 (1976) · Zbl 0336.93039 |
| [34] | Traub, J. F., Iterative Methods for the Solution of Equations (1964), Prentice-Hall, Englewood Cliffs, New Jersey · Zbl 0121.11204 |
| [35] | Soleymani, F., On finding robust approximate inverses for large sparse matrices, Linear Multilinear Algebra, 62, 1314-1334 (2014) · Zbl 1317.65081 |
| [36] | Petković, M. D.; Petković, M. S., Hyper-power methods for the computation of outer inverses, J. Comput. Appl. Math., 278, 110-118 (2015) · Zbl 1304.65135 |
| [37] | Petković, M. D., Generalized Schultz iterative methods for the computation of outer inverses, Comput. Math. Appl., 67, 1837-1847 (2014) · Zbl 1367.65040 |
| [38] | Sharifi, M.; Arab, M.; Khaksar Haghani, F., Finding generalized inverses by a fast and efficient numerical method, J. Comput. Appl. Math., 279, 187-191 (2015) · Zbl 1306.65191 |
| [39] | Soleimani, F.; Stanimirović, P. S.; Soleymani, F., Some matrix iterations for computing generalized inverses and balancing chemical equations, Algorithms, 8, 982-998 (2015) · Zbl 1461.65059 |
| [40] | Soleymani, F., An efficient and stable Newton-type iterative method for computing generalized inverse \(A_{T , S}^{( 2 )}\), Numer. Algorithms, 69, 569-578 (2015) · Zbl 1335.65043 |
| [41] | Soleymani, F.; Stanimirović, P. S.; Khaksar Haghani, F., On hyperpower family of iterations for computing outer inverses possessing high efficiencies, Linear Algebra Appl., 484, 477-495 (2015) · Zbl 1327.65087 |
| [42] | Ghorbanzadeh, M.; Mahdiani, K.; Soleymani, F.; Lotfi, T., A class of Kung-Traub-type iterative algorithms for matrix inversion, Int. J. Appl. Comput. Math., 2, 641-648 (2016) · Zbl 1420.65033 |
| [43] | Pan, V. Y.; Soleymani, F.; Zhao, L., An efficient computation of generalized inverse of a matrix, Appl. Math. Comput., 316, 89-101 (2018) · Zbl 1426.65040 |
| [44] | Kumar, A.; Stanimirović, P. S.; Soleymani, F.; Krstić, M.; Rajković, K., Factorizations of hyperpower family of iterative methods via least squares approach, J. Comput. Appl. Math., 37, 3226-3240 (2018) · Zbl 1416.65104 |
| [45] | Piegl, L.; Tiller, W., (The NURBS Book. The NURBS Book, Monographs in Visual Communications (1997), Springer Berlin Heidelberg) · Zbl 0868.68106 |
| [46] | Petković, M. D.; Krstić, M. A.; Rajković, K. P., Rapid generalized Schultz iterative methods for the computation of outer inverses, J. Comput. Appl. Math., 344, 572-584 (2018) · Zbl 1451.65040 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
