Parallel Minimum Norm Solution of Sparse Block Diagonal Column Overlapped Underdetermined Systems

Download
2017-03-01
Torun, F. Sukru
Manguoğlu, Murat
Aykanat, Cevdet
Underdetermined systems of equations in which the minimum norm solution needs to be computed arise in many applications, such as geophysics, signal processing, and biomedical engineering. In this article, we introduce a new parallel algorithm for obtaining the minimum 2-norm solution of an underdetermined system of equations. The proposed algorithm is based on the Balance scheme, which was originally developed for the parallel solution of banded linear systems. The proposed scheme assumes a generalized banded form where the coefficient matrix has column overlapped block structure in which the blocks could be dense or sparse. In this article, we implement the more general sparse case. The blocks can be handled independently by any existing sequential or parallel QR factorization library. A smaller reduced system is formed and solved before obtaining the minimum norm solution of the original system in parallel. We experimentally compare and confirm the error bound of the proposed method against the QR factorization based techniques by using true single-precision arithmetic. We implement the proposed algorithm by using the message passing paradigm. We demonstrate numerical effectiveness as well as parallel scalability of the proposed algorithm on both shared and distributed memory architectures for solving various types of problems.
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE

Suggestions

Parallelization of a transient method of lines Navier-Stokes code
Ersahin, C; Tarhan, T; Tuncer, İsmail Hakkı; Selçuk, Nevin (2004-01-01)
Parallel implementation of a serial code, namely method of lines ( MOL) solution for momentum equations (MOLS4ME), previously developed for the solution of transient Navier - Stokes equations for incompressible separated internal flows in regular and complex geometries, is described.
A Multithreaded Recursive and Nonrecursive Parallel Sparse Direct Solver
Bölükbaşı, Ercan Selçuk (2016-01-01)
Sparse linear system of equations often arises after discretization of the partial differential equations (PDEs) such as computational fluid dynamics, material science, and structural engineering. There are, however, sparse linear systems that are not governed by PDEs, some examples of such applications are circuit simulations, power network analysis, and social network analysis. For solution of sparse linear systems one can choose using either a direct or an iterative method. Direct solvers are based on so...
Multi-symplectic integration of coupled non-linear Schrodinger system with soliton solutions
AYDIN, AYHAN; Karasözen, Bülent (2009-01-01)
Systems of coupled non-linear Schrodinger equations with soliton solutions are integrated using the six-point scheme which is equivalent to the multi-symplectic Preissman scheme. The numerical dispersion relations are studied for the linearized equation. Numerical results for elastic and inelastic soliton collisions are presented. Numerical experiments confirm the excellent conservation of energy, momentum and norm in long-term computations and their relations to the qualitative behaviour of the soliton sol...
Distributed Optimal Control Problems Governed by Coupled Convection Dominated PDEs with Control Constraints
Yücel, Hamdullah (2013-08-30)
We study the numerical solution of control constrained optimal control problems governed by a system of convection diffusion equations with nonlinear reaction terms, arising from chemical processes. Control constraints are handled by using the primal-dual active set algorithm as a semi-smooth Newton method or by adding a Moreau-Yosida-type penalty function to the cost functional. An adaptive mesh refinement indicated by a posteriori error estimates is applied for both approaches.
Parallel processing of two-dimensional euler equations for compressible flows
Doǧru, K.; Aksel, M.h.; Tuncer, İsmail Hakkı (2008-12-01)
A parallel implementation of a previously developed finite volume algorithm for the solution of two-dimensional, unsteady, compressible Euler equations is given. The conservative form of the Euler equations is discretized with a second order accurate, one-step Lax-Wendroff scheme. Local time stepping is utilized in order to accelerate the convergence. For the parallel implementation of the method, the solution domain is partitioned into a number of subdomains to be distributed to separate processors for par...
Citation Formats
F. S. Torun, M. Manguoğlu, and C. Aykanat, “Parallel Minimum Norm Solution of Sparse Block Diagonal Column Overlapped Underdetermined Systems,” ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, pp. 0–0, 2017, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/39747.