Title | ||
---|---|---|
Performance modeling of multishift QR algorithms for the parallel solution of symmetric tridiagonal eigenvalue problems |
Abstract | ||
---|---|---|
Multishift QR algorithms are efficient for solving the symmetric tridiagonal eigenvalue problem on a parallel computer. In this paper, we focus on three variants of the multishift QR algorithm, namely, the conventional multishift QR algorithm, the deferred shift QR algorithm and the fully pipelined multishift QR algorithm, and construct performance models for them. Our models are designed for shared-memory parallel machines, and given the basic performance characteristics of the target machine and the problem size, predict the execution time of these algorithms. Experimental results show that our models can predict the relative performance of these algorithms to the accuracy of 10% in many cases. Thus our models are useful for choosing the best algorithm to solve a given problem in a specified computational environment, as well as for finding the best value of the performance parameters. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1007/978-3-642-13136-3_41 | ICA3PP (2) |
Keywords | Field | DocType |
symmetric tridiagonal eigenvalue problem,problem size,conventional multishift qr algorithm,performance modeling,relative performance,best algorithm,multishift qr algorithm,parallel solution,performance parameter,performance model,deferred shift qr algorithm,basic performance characteristic,shared memory,parallel computer | Tridiagonal matrix,Computer science,Parallel computing,Algorithm,Execution time,Divide-and-conquer eigenvalue algorithm,Eigenvalues and eigenvectors,QR algorithm | Conference |
Volume | ISSN | ISBN |
6082 | 0302-9743 | 3-642-13135-2 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Takafumi Miyata | 1 | 1 | 1.39 |
Yusaku Yamamoto | 2 | 52 | 20.61 |
Shao-Liang Zhang | 3 | 92 | 19.06 |