Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
least square problem; domain decomposition; redundant multipliers
least square problem; domain decomposition; redundant multipliers
Summary:
The variants of FETI (finite element tearing and interconnecting) based domain decomposition methods are well-established, massively parallel algorithms for solving huge linear systems arising from the discretization of elliptic partial differential equations. Here, we adapt the FETI method for solving the large least squares problems associated with inconsistent systems of linear equations arising from the discretization of elliptic partial differential equations. We briefly review the symmetric least squares problems and the FETI method, explain how FETI can find the least squares solution, prove the optimal rate of convergence, and present the results of numerical experiments demonstrating the efficiency of the proposed method in solving the least squares problem defined by the Poisson equation with inconsistent Neumann conditions.
References:
[1] Arbenz, P., Drmač, Z.: On positive semidefinite matrices with known null space. SIAM J. Matrix Anal. Appl. 24 (2002), 132-149. DOI 10.1137/S0895479800381331 | MR 1920559 | Zbl 1032.65025
[2] Björck, \r A.: Numerical Methods for Least Squares Problems. SIAM, Philadelphia (1996). DOI 10.1137/1.9781611971484 | MR 1386889 | Zbl 0847.65023
[3] Blaheta, R., Jakl, O., Starý, J., Krečmer, K.: Schwarz DD method for analysis of geocomposites. Proceedings of the 12th International Conference on Civil, Structural and Environmental Engineering Computing Civil-Comp Press, Stirlingshire (2009), Article ID 111.
[4] Calvetti, D., Reichel, L., Zhang, Q.: Conjugate gradient algorithms for symmetric inconsistent linear systems. Proceedings of the Lanczos Centenary Conference SIAM, Philadelphia (1994), 267-272.
[5] Choi, C. T., Saunders, M. A.: Algorithm 937: MINRES-QLP for symmetric and Hermitian linear equations and least-squares problems. ACM Trans. Math. Softw. 40 (2014), Article ID 16, 12 pages \99999DOI99999 10.1145/252726 . MR 3181906 | Zbl 1305.65117
[6] Dostál, Z., Brzobohatý, T., Horák, D., Kružík, J., Vlach, O.: Scalable hybrid TFETI-DP methods for large boundary variational inequalities. Domain Decomposition Methods in Science and Engineering XXVI Lecture Notes in Computational Science and Engineering 145. Springer, Cham (2022), 29-40. DOI 10.1007/978-3-030-95025-5_3 | MR 4703833 | Zbl 07936273
[7] Dostál, Z., Horák, D., Brzobohatý, T., Vodstrčil, P.: Bounds on the spectra of Schur complements of large H-TFETI-DP clusters for 2D Laplacian. Numer. Linear Algebra Appl. 28 (2021), Article ID e2344, 15 pages. DOI 10.1002/nla.2344 | MR 4211729 | Zbl 1549.65522
[8] Dostál, Z., Horák, D., Kučera, R.: Total FETI -- an easier, implementable variant of the FETI method for the numerical solution of elliptic PDE. Commun. Numer. Methods Eng. 22 (2006), 1155-1162. DOI 10.1002/cnm.881 | MR 2282408 | Zbl 1107.65104
[9] Dostál, Z., Kozubek, T., Markopoulos, A., Menšík, M.: Cholesky decomposition of a positive semidefinite matrix with known kernel. Appl. Math. Comput. 217 (2011), 6067-6077. DOI 10.1016/j.amc.2010.12.069 | MR 2773349 | Zbl 1211.65034
[10] Dostál, Z., Pospíšil, L.: Conjugate gradients for symmetric positive semidefinite least-squares problems. Int. J. Comput. Math. 95 (2018), 2229-2239. DOI 10.1080/00207160.2017.1371701 | MR 3844674 | Zbl 1499.65114
[11] Farhat, C., Mandel, J., Roux, F.-X.: Optimal convergence properties of the FETI domain decomposition method. Comput. Methods Appl. Mech. Eng. 115 (1994), 365-385 \99999DOI99999 10.1016/0045-7825(94)90068-X . MR 1285024
[12] Farhat, C., Roux, F.-X.: A method of finite element tearing and interconnecting and its parallel solution algorithm. Int. J. Numer. Methods Eng. 32 (1991), 1205-1227 \99999DOI99999 10.1002/nme.1620320604 . MR 3618550 | Zbl 0758.65075
[13] Farhat, C., Roux, F.-X.: An unconventional domain decomposition method for an efficient parallel solution of large-scale finite element systems. SIAM J. Sci. Stat. Comput. 13 (1992), 379-396. DOI 10.1137/0913020 | MR 1145192 | Zbl 0746.65086
[14] Fong, D. C.-L., Saunders, M. A.: LSMR: An iterative algorithm for sparse least-squares problems. SIAM J. Sci. Comput. 33 (2011), 2950-2971. DOI 10.1137/10079687X | MR 2861656 | Zbl 1232.65052
[15] Karypis, G., Kumar, V.: METIS: Serial Graph Partitioning and Fill-reducing Matrix Ordering. Available at https://github.com/KarypisLab/METIS
[16] Klawonn, A., Rheinbach, O.: A hybrid approach to 3-level FETI. PAMM, Proc. Appl. Math. Mech. 8 (2008), 10841-10843. DOI 10.1002/pamm.200810841 | Zbl 1392.65114
[17] Kruis, J.: Domain Decomposition Methods for Distributed Computing. Saxe-Cobourg Publications, Stirling (2006).
[18] Paige, C. C., Saunders, M. A.: LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Softw. 8 (1982), 43-71. DOI 10.1145/355984.3559 | MR 0661121 | Zbl 0478.65016
[19] Saad, Y.: Iterative Methods for Sparse Linear Systems. SIAM, Philadelphia (2003). DOI 10.1137/1.9780898718003 | MR 1990645 | Zbl 1031.65046
[20] Toselli, A., Widlund, O. B.: Domain Decomposition Methods: Algorithms and Theory. Springer Series on Computational Mathematics 34. Springer, Berlin (2005). DOI 10.1007/b137868 | MR 2104179 | Zbl 1069.65138
[21] Xin, K., Meng, L.: Block-splitting preconditioners for indefinite least squares problem. Comput. Appl. Math. 44 (2025), Article ID 61, 17 pages. DOI 10.1007/s40314-024-03016-7 | MR 4834472 | Zbl 1563.65174
Search
Partner of
