Show simple item record

dc.contributor.author
Wicky, Tobias
dc.date.accessioned
2017-10-03T14:00:45Z
dc.date.available
2017-06-12T03:54:46Z
dc.date.available
2017-10-03T14:00:45Z
dc.date.issued
2015
dc.identifier.uri
http://hdl.handle.net/20.500.11850/114967
dc.identifier.doi
10.3929/ethz-a-010686133
dc.description.abstract
In this work an algorithm for solving triangular systems of equations for multiple right hand sides is presented. The algorithm for solving triangular systems for multiple right hand sides, commonly referred to as the TRSM problem, is a very important in dense linear algebra as it is a subroutine for most decompositions of matrices as LU or QR. To improve performance over the standard iterative algorithms for TRSM, a block wise inversion paired with triangular matrix multiplications is used. To perform the inversion, the lower triangular form of the matrix is exploited and a recursive scheme is applied to further decrease communication cost. With that, the latency of the algorithm decreases while the bandwidth and floating point operations count stay asymptotically the same. Concretely, a decrease of latency with a factor of p^{2/3} / log p was achieved for a significant range of relative matrix sizes when working with p processors. The proposed method is implemented and its performance is benchmarked against the widely used ScaLAPACK library. The results show promising tendencies for the inversion, with a maximal speedup of 1.7 over ScaLAPACK for 4096 processors. Due to the inferior performance of triangular matrix multiplications with respect to the triangular solve, no overall improvement is made yet.
en_US
dc.language.iso
en
en_US
dc.publisher
ETH Zürich
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.subject
EXAMINATION PAPERS + DEGREE PAPERS (DOCUMENT TYPES)
en_US
dc.subject
PARALLELE NUMERIK (NUMERISCHE MATHEMATIK)
en_US
dc.subject
ITERATIVE METHODS (NUMERICAL MATHEMATICS)
en_US
dc.subject
MATRIX EQUATIONS (ALGEBRA)
en_US
dc.subject
DIPLOMARBEITEN UND EXAMENSARBEITEN (DOKUMENTENTYP)
en_US
dc.subject
MATRIX INVERSION (NUMERICAL MATHEMATICS)
en_US
dc.subject
ITERATIVE VERFAHREN (NUMERISCHE MATHEMATIK)
en_US
dc.subject
PARALLEL COMPUTING (NUMERICAL MATHEMATICS)
en_US
dc.subject
MATRIZENGLEICHUNGEN (ALGEBRA)
en_US
dc.subject
MATRIZENINVERSION (NUMERISCHE MATHEMATIK)
en_US
dc.title
Communication-Avoiding Parallel Algorithms for Solving Triangular Matrix Equations
en_US
dc.type
Bachelor Thesis
dc.rights.license
In Copyright - Non-Commercial Use Permitted
dc.date.published
2016
ethz.size
42 p.
en_US
ethz.code.ddc
5 - Science::510 - Mathematics
en_US
ethz.identifier.nebis
010686133
ethz.publication.place
Zürich
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::01434 - Lehre Mathematik::01431 - SR Rechnergestützte Wissenschaften::01405 - BSc Rechnergestützte Wissenschaften / BSc Computational Science and Engin.
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics
en_US
ethz.date.deposited
2017-06-12T03:59:11Z
ethz.source
ECOL
ethz.source
ECIT
ethz.identifier.importid
imp59366b96d6d6890735
ethz.identifier.importid
imp59365449ebd7693946
ethz.ecolpid
eth:49453
ethz.ecitpid
pub:176776
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-07-31T16:40:17Z
ethz.rosetta.lastUpdated
2017-10-03T14:00:51Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Communication-Avoiding%20Parallel%20Algorithms%20for%20Solving%20Triangular%20Matrix%20Equations&rft.date=2015&rft.au=Wicky,%20Tobias&rft.genre=unknown&rft.btitle=Communication-Avoiding%20Parallel%20Algorithms%20for%20Solving%20Triangular%20Matrix%20Equations
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record