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

Download

index.pdf

Date

2017-03-01

Author

Torun, F. Sukru
Manguoğlu, Murat
Aykanat, Cevdet

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

202
views

0
downloads

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.

Subject Keywords

Minimum norm solution, Underdetermined least square problems, Parallel algorithms, Balance method

URI

https://hdl.handle.net/11511/39747

Journal

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE

DOI

https://doi.org/10.1145/3004280

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

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...
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...

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.