Applications of Mathematics, Vol. 70, No. 6, pp. 929-939, 2025
The least squares solution of inconsistent discretized elliptic problems using the FETI method
Zdeněk Dostál, David Horák
Received August 5, 2025. Published online December 4, 2025.
Abstract: 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.
Keywords: least square problem; domain decomposition; redundant multipliers
References: [1] P. Arbenz, Z. Drmač: 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: Numerical Methods for Least Squares Problems. SIAM, Philadelphia (1996). DOI 10.1137/1.9781611971484 | MR 1386889 | Zbl 0847.65023
[3] R. Blaheta, O. Jakl, J. Starý, K. Krečmer: 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] D. Calvetti, L. Reichel, Q. Zhang: Conjugate gradient algorithms for symmetric inconsistent linear systems. Proceedings of the Lanczos Centenary Conference. SIAM, Philadelphia (1994), 267-272.
[5] C. T. Choi, M. A. Saunders: 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. DOI 10.1145/252726 | MR 3181906 | Zbl 1305.65117
[6] Z. Dostál, T. Brzobohatý, D. Horák, J. Kružík, O. Vlach: 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] Z. Dostál, D. Horák, T. Brzobohatý, P. Vodstrčil: 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] Z. Dostál, D. Horák, R. Kučera: 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] Z. Dostál, T. Kozubek, A. Markopoulos, M. Menšík: 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] Z. Dostál, L. Pospíšil: 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] C. Farhat, J. Mandel, F.-X. Roux: Optimal convergence properties of the FETI domain decomposition method. Comput. Methods Appl. Mech. Eng. 115 (1994), 365-385. DOI 10.1016/0045-7825(94)90068-X | MR 1285024
[12] C. Farhat, F.-X. Roux: A method of finite element tearing and interconnecting and its parallel solution algorithm. Int. J. Numer. Methods Eng. 32 (1991), 1205-1227. DOI 10.1002/nme.1620320604 | MR 3618550 | Zbl 0758.65075
[13] C. Farhat, F.-X. Roux: 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] D. C.-L. Fong, M. A. Saunders: 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] G. Karypis, V. Kumar: METIS: Serial Graph Partitioning and Fill-reducing Matrix Ordering. Available at https://github.com/KarypisLab/METIS. SW 4089
[16] A. Klawonn, O. Rheinbach: 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] J. Kruis: Domain Decomposition Methods for Distributed Computing. Saxe-Cobourg Publications, Stirling (2006).
[18] C. C. Paige, M. A. Saunders: 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] Y. Saad: Iterative Methods for Sparse Linear Systems. SIAM, Philadelphia (2003). DOI 10.1137/1.9780898718003 | MR 1990645 | Zbl 1031.65046
[20] A. Toselli, O. B. Widlund: 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] K. Xin, L. Meng: 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
Affiliations: Zdeněk Dostál, Department of Applied Mathematics, FEECS, VSB - Technical University of Ostrava, 17. listopadu 2172/15, 708 33 Ostrava-Poruba, Czech Republic, e-mail: zdenek.dostal@vsb.cz; David Horák (corresponding author), Department of Applied Mathematics, FEECS, VSB - Technical University of Ostrava, 17. listopadu 2172/15, 708 33 Ostrava-Poruba, Czech Republic; Institute of Geonics of the Czech Academy of Sciences, Studentská 1768/9, 708 00 Ostrava-Poruba, Czech Republic, e-mail: david.horak@vsb.cz
