| 1. |
- Kjelgaard Mikkelsen, Carl Christian, 1976-, et al.
(författare)
-
Parallel robust solution of triangular linear systems
- 2019
-
Ingår i: Concurrency and Computation. - : John Wiley & Sons. - 1532-0626 .- 1532-0634. ; 31:19
-
Tidskriftsartikel (refereegranskat)abstract
- Triangular linear systems are central to the solution of general linear systems and the computation of eigenvectors. In the absence of floating‐point exceptions, substitution runs to completion and solves a system which is a small perturbation of the original system. If the matrix is well‐conditioned, then the normwise relative error is small. However, there are well‐conditioned systems for which substitution fails due to overflow. The robust solvers xLATRS from LAPACK extend the set of linear systems which can be solved by dynamically scaling the solution and the right‐hand side to avoid overflow. These solvers are sequential and apply to systems with a single right‐hand side. This paper presents algorithms which are blocked and parallel. A new task‐based parallel robust solver (Kiya) is presented and compared against both DLATRS and the non‐robust solvers DTRSV and DTRSM. When there are many right‐hand sides, Kiya performs significantly better than the robust solver DLATRS and is not significantly slower than the non‐robust solver DTRSM.
|
|
| 2. |
|
|
| 3. |
- Schwarz, Angelika Beatrix, 1989-
(författare)
-
Improving the efficiency of eigenvector-related computations
- 2021
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- An effective strategy in dense linear algebra is the design of algorithms as tiled algorithms. Tiled algorithms that express the bulk of the computation as matrix-matrix operations (level-3 BLAS) have proven successful in achieving high performance on cache-based architectures. At the same time, tiled algorithms interoperate with dynamic data-driven execution models such as task parallelism and promise good parallel scalability.This thesis applies the concept of tiled algorithms and task-centric execution to algorithms related to the computation of eigenvectors for the dense, non-symmetric eigenvalue problem. First, a standard algorithm for computing eigenvectors from the Schur form is recast such that all computational steps are rich in matrix-matrix operations. Second, inverse iteration on the Hessenberg matrix as an alternative approach to computing eigenvectors is addressed. An existing algorithm is revised to express the computationally most expensive step with matrix-matrix operations. Third, a task-parallel, tiled triangular Sylvester equation solver is amended to solve a larger class of problems. All algorithms have an enhanced performance, which is demonstrated through numerical experiments.
|
|
| 4. |
- Schwarz, Angelika Beatrix, 1989-
(författare)
-
Robust level-3 blas inverse iteration from the Hessenberg matrix
- 2022
-
Ingår i: ACM Transactions on Mathematical Software. - : ACM Digital Library. - 0098-3500 .- 1557-7295. ; 48:3
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract
- Inverse iteration is known to be an effective method for com-puting eigenvectors corresponding to simple and well-separated eigenvalues. In the non-symmetric case, the solution of shifted Hessenberg systems is a central step. Existing inverse iteration solvers approach the solution of the shiftedHessenberg systems with either RQ or LU factorizations and, once factored, solve the corresponding systems. This approach has limited level-3 BLAS potential since distinct shifts have distinct factorizations. This paper rearranges the RQ approach such that data shared between distinct shifts is exposed. Thereby the backward substitution with the triangular R factor can be expressed mostly with matrix–matrix multiplications (level-3 BLAS). The resulting algorithm computes eigenvectors in a tiled, overflow-free, and task-parallel fashion. The numerical experiments show that the new algorithm outperforms existing inverse iteration solvers for the computation of both real and complex eigenvectors.
|
|
| 5. |
- Schwarz, Angelika Beatrix, 1989-, et al.
(författare)
-
Robust parallel eigenvector computation for the non-symmetric eigenvalue problem
- 2020
-
Ingår i: Parallel Computing. - : Elsevier. - 0167-8191 .- 1872-7336. ; 100
-
Tidskriftsartikel (refereegranskat)abstract
- A standard approach for computing eigenvectors of a non-symmetric matrix reduced to real Schur form relies on a variant of backward substitution. Backward substitution is prone to overflow. To avoid overflow, the LAPACK eigenvector routine DTREVC3 associates every eigenvector with a scaling factor and dynamically rescales an entire eigenvector during the backward substitution such that overflow cannot occur. When many eigenvectors are computed, DTREVC3 applies backward substitution successively for every eigenvector. This corresponds to level-2 BLAS operations and constitutes a bottleneck. This paper redesigns the backward substitution such that the entire computation is cast as tile operations (level-3 BLAS). By replacing LAPACK’s scaling factor with tile-local scaling factors, our solver decouples the tiles and sustains parallel scalability even when a lot of numerical scaling is necessary.
|
|
| 6. |
- Schwarz, Angelika Beatrix, et al.
(författare)
-
Robust Task-Parallel Solution of the Triangular Sylvester Equation
- 2020
-
Ingår i: Parallel Processing and Applied Mathematics. - Cham : Springer. - 9783030432287 - 9783030432294 ; , s. 82-92
-
Konferensbidrag (refereegranskat)abstract
- The Bartels-Stewart algorithm is a standard approach to solving the dense Sylvester equation. It reduces the problem to the solution of the triangular Sylvester equation. The triangular Sylvester equation is solved with a variant of backward substitution. Backward substitution is prone to overflow. Overflow can be avoided by dynamic scaling of the solution matrix. An algorithm which prevents overflow is said to be robust. The standard library LAPACK contains the robust scalar sequential solver dtrsyl. This paper derives a robust, level-3 BLAS-based task-parallel solver. By adding overflow protection, our robust solver closes the gap between problems solvable by LAPACK and problems solvable by existing non-robust task-parallel solvers. We demonstrate that our robust solver achieves a performance similar to non-robust solvers.
|
|
| 7. |
- Schwarz, Angelika Beatrix, et al.
(författare)
-
Scalable eigenvector computation for the non-symmetric eigenvalue problem
- 2019
-
Ingår i: Parallel Computing. - : Elsevier. - 0167-8191 .- 1872-7336. ; 85, s. 131-140
-
Tidskriftsartikel (refereegranskat)abstract
- We present two task-centric algorithms for computing selected eigenvectors of a non-symmetric matrix reduced to real Schur form. Our approach eliminates the sequential phases present in the current LAPACK/ScaLAPACK implementation. We demonstrate the scalability of our implementation on multicore, manycore and distributed memory systems.
|
|
| 8. |
- Schwarz, Angelika Beatrix, 1989-
(författare)
-
Towards efficient overflow-free solvers for systems of triangular type
- 2019
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Triangular linear systems are fundamental in numerical linear algebra. A triangular linear system has a straight-forward and efficient solution strategy, namely forward substitution for lower triangular systems and backward substitution for upper triangular systems. Triangular systems, or, more generally, systems of triangular type occur frequently in algorithms for more complex problems. This thesis addresses three systems that involve linear systems of triangular type. The first system concerns quasi-triangular matrices. Quasi-triangular matrices are block triangular with 1-by-1 and 2-by-2 blocks on the diagonal. Quasi-triangular systems arise in the computation of eigenvectors from the real Schur form for the non-symmetric eigenvalue problem. This thesis contributes two algorithms for the eigenvector computation, which solve shifted quasi-triangular linear systems in an efficient and scalable way. The second system addresses scaled triangular linear systems. During the solution of a triangular linear system, the entries of the solution can grow. This growth can exceed the representable range of floating-point numbers. Such an overflow can be avoided by solving a scaled triangular system. The solution is scaled prior to every operation that would otherwise result in an overflow. After scaling, the operations can be executed safely. This thesis analyzes the scalability of a recently developed tiled, robust solver for scaled triangular systems, which ensures that at no point in the computation the overflow threshold is exceeded. The third system tackles the scaled continuous-time triangular Sylvester equation, which couples two quasi-triangular matrices. The solution process is prone to overflow. This thesis contributes a robust, tiled solver and demonstrates its practicability. These three systems can be addressed with a variation of forward or backward substitution. Compared to the highly optimized and scalable implementations of standard forward and backward substitution available in HPC libraries,the existing implementations of these three systems run at a smaller fraction of the peak performance. This thesis presents techniques to improve on the performance and robustness of the implementations of the three systems.
|
|
