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.
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...
Solving optimal control time-dependent diffusion-convection-reaction equations by space time discretizations
Seymen, Zahire; Karasözen, Bülent; Department of Mathematics (2013)
Optimal control problems (OCPs) governed by convection dominated diffusion-convection-reaction equations arise in many science and engineering applications such as shape optimization of the technological devices, identification of parameters in environmental processes and flow control problems. A characteristic feature of convection dominated optimization problems is the presence of sharp layers. In this case, the Galerkin finite element method performs poorly and leads to oscillatory solutions. Hence, thes...
PARALLEL IMPLEMENTATION OF MLFMA FOR HOMOGENEOUS OBJECTS WITH VARIOUS MATERIAL PROPERTIES
Ergül, Özgür Salih (2011-01-01)
We present a parallel implementation of the multilevel fast multipole algorithm (MLFMA) for fast and accurate solutions of electromagnetics problems involving homogeneous objects with diverse material properties. Problems are formulated rigorously with the electric and magnetic current combined-field integral equation (JMCFIE) and solved iteratively using MLFMA parallelized with the hierarchical partitioning strategy. Accuracy and efficiency of the resulting implementation are demonstrated on canonical prob...
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...
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.