Numerical analysis of parallel implementation of the reorthogonalized ABS methods

Szabina Fodor and Zoltán Németh ()
Additional contact information
Zoltán Németh: Corvinus University of Budapest

Central European Journal of Operations Research, 2019, vol. 27, issue 2, No 10, 437-454

Abstract: Abstract Solving systems of equations is a critical step in various computational tasks. We recently published a novel ABS-based reorthogonalization algorithm to compute the QR factorization. Experimental analysis on the Matlab 2015a platform revealed that this new ABS-based algorithm was able to more accurately calculate the rank of the coefficient matrix, the determination of the orthogonal bases and the QR factorization than the built-in rank or qr Matlab functions. However, the reorthogonalization process significantly increased the computation cost. Therefore, we tested a new approach to accelerate this algorithm by implementing it on different parallel platforms. The above mentioned ABS-based reorthogonalization algorithm was implemented using Matlab’s parallel computing toolbox and accelerated massive parallelism (AMP) runtime library. We have tested various matrices including Pascal, Vandermonde and randomly generated dense matrices. The performance of the parallel algorithm was determined by calculating the speed-up factor defined as the fold reduction of execution time compared to the sequential algorithm. For comparison, we also tested the effect of parallel implementation of the classical Gram–Schmidt algorithm incorporating a reorthogonalization step. The results show that the achieved speed-up is significant, and also the performance of this practical parallel algorithm increases as the number of equations grows. The results reveal that the reorthogonalized ABS algorithm is practical and efficient. This fact expands the practical usefulness of our algorithms.

Keywords: ABS methods; Rank-revealing QR; Reorthogonalization; Parallel computing (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10100-018-0557-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:cejnor:v:27:y:2019:i:2:d:10.1007_s10100-018-0557-4

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10100

DOI: 10.1007/s10100-018-0557-4

Access Statistics for this article

Central European Journal of Operations Research is currently edited by Ulrike Leopold-Wildburger

More articles in Central European Journal of Operations Research from Springer, Slovak Society for Operations Research, Hungarian Operational Research Society, Czech Society for Operations Research, Österr. Gesellschaft für Operations Research (ÖGOR), Slovenian Society Informatika - Section for Operational Research, Croatian Operational Research Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().