Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
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
67
views
0
downloads
Cite This
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...
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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
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.