umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Parallel Reduction from Block Hessenberg to Hessenberg using MPI
Umeå University, Faculty of Science and Technology, Department of Computing Science.
2013 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

In many scientific applications, eigenvalues of a matrix have to be computed. By first reducing a matrix from fully dense to Hessenberg form, eigenvalue computations with the QR algorithm become more effcient. Previous work on shared memory architectures has shown that the Hessenberg reduction is in some cases most effcient when performed in two stages: First reduce the matrix to block Hessenberg form, then reduce the block Hessenberg matrix to true Hessenberg form. This Thesis concerns the adaptation of an existing parallel reduction algorithm implementing the second stage to a distributed memory architecture. Two algorithms were designed using the Message Passing Interface (MPI) for communication between processes. The algorithms have been evaluated by an analyze of trace and run-times for different problem sizes and processes. Results show that the two adaptations are not effcient compared to a shared memory algorithm, but possibilities for further improvement have been identified. We found that an uneven distribution of work, a large sequential part, and significant communication overhead are the main bottlenecks in the distributed algorithms. Suggested further improvements are dynamic load balancing, sequential computation overlap, and hidden communication.

Place, publisher, year, edition, pages
2013.
Series
UMNAD, 949
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:umu:diva-80687OAI: oai:DiVA.org:umu-80687DiVA: diva2:650907
Educational program
Master of Science Programme in Computing Science and Engineering
Supervisors
Examiners
Available from: 2013-09-24 Created: 2013-09-24 Last updated: 2013-09-24Bibliographically approved

Open Access in DiVA

fulltext(1333 kB)525 downloads
File information
File name FULLTEXT01.pdfFile size 1333 kBChecksum SHA-512
548f6fa3f5cc281a4b0b042a123618a43f5cbb426065b3f9b47ee0a5b5c8d8ffe66d4f0c1b372ddb80441bcb38368af842a36d7fec0f736e3618a2fb47395af4
Type fulltextMimetype application/pdf

By organisation
Department of Computing Science
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 525 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 193 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf