umu.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Kågström, Bo
Alternative names
Publications (10 of 89) Show all publications
Adlerborn, B., Karlsson, L. & Kågström, B. (2018). Distributed one-stage Hessenberg-triangular reduction with wavefront scheduling. SIAM Journal on Scientific Computing, 40(2), C157-C180
Open this publication in new window or tab >>Distributed one-stage Hessenberg-triangular reduction with wavefront scheduling
2018 (English)In: SIAM Journal on Scientific Computing, ISSN 1064-8275, E-ISSN 1095-7197, Vol. 40, no 2, p. C157-C180Article in journal (Refereed) Published
Abstract [en]

A novel parallel formulation of Hessenberg-triangular reduction of a regular matrix pair on distributed memory computers is presented. The formulation is based on a sequential cacheblocked algorithm by K degrees agstrom et al. [BIT, 48 (2008), pp. 563 584]. A static scheduling algorithm is proposed that addresses the problem of underutilized processes caused by two-sided updates of matrix pairs based on sequences of rotations. Experiments using up to 961 processes demonstrate that the new formulation is an improvement of the state of the art and also identify factors that limit its scalability.

Place, publisher, year, edition, pages
Society for Industrial and Applied Mathematics, 2018
Keywords
generalized eigenvalue problem, Hessenberg-triangular reduction, parallel algorithms, wavefront scheduling
National Category
Computational Mathematics
Identifiers
urn:nbn:se:umu:diva-147843 (URN)10.1137/16M1103890 (DOI)000431100400039 ()
Available from: 2018-05-18 Created: 2018-05-18 Last updated: 2018-06-09Bibliographically approved
Eljammaly, M., Karlsson, L. & Kågström, B. (2017). An auto-tuning framework for a NUMA-aware Hessenberg reduction algorithm. Umeå: Department of computing science, Umeå university
Open this publication in new window or tab >>An auto-tuning framework for a NUMA-aware Hessenberg reduction algorithm
2017 (English)Report (Other academic)
Abstract [en]

The performance of a recently developed Hessenberg reduction algorithm greatly depends on the values chosen for its tunable parameters. The search space is huge combined with other complications makes the problem hard to solve effectively with generic methods and tools. We describe a modular auto-tuning framework in which the underlying optimization algorithm is easy to substitute. The framework exposes sub-problems of standard auto-tuning type for which existing generic methods can be reused. The outputs of concurrently executing sub-tuners are assembled by the framework into a solution to the original problem.

Place, publisher, year, edition, pages
Umeå: Department of computing science, Umeå university, 2017. p. 14
Series
Report / UMINF, ISSN 0348-0542 ; 17.19
Keywords
Auto-tuning, Tuning framework, Binning, Search space decomposition, Multistage search, Hessenberg reduction, NUMA-aware
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-145297 (URN)
Available from: 2018-02-28 Created: 2018-02-28 Last updated: 2018-06-09Bibliographically approved
Dmytryshyn, A., Johansson, S. & Kågström, B. (2017). Canonical structure transitions of system pencils. SIAM Journal on Matrix Analysis and Applications, 38(4), 1249-1267
Open this publication in new window or tab >>Canonical structure transitions of system pencils
2017 (English)In: SIAM Journal on Matrix Analysis and Applications, ISSN 0895-4798, E-ISSN 1095-7162, Vol. 38, no 4, p. 1249-1267Article in journal (Refereed) Published
Abstract [en]

We investigate the changes of the canonical structure information under small perturbations for a system pencil associated with a (generalized) linear time-invariant state-space system. The equivalence class of the pencil is taken with respect to feedback-injection equivalence transformations. The results allow us to track possible changes of important linear system characteristics under small perturbations.

Place, publisher, year, edition, pages
Society for Industrial and Applied Mathematics, 2017
National Category
Mathematics Computer and Information Sciences
Research subject
Computing Science
Identifiers
urn:nbn:se:umu:diva-139924 (URN)10.1137/16M1097857 (DOI)000418665600009 ()
Funder
Swedish Research Council, E0485301Swedish Research Council, eSSENCE
Available from: 2017-09-26 Created: 2017-09-26 Last updated: 2018-06-09Bibliographically approved
Eljammaly, M., Karlsson, L. & Kågström, B. (2017). On the Tunability of a New Hessenberg Reduction Algorithm Using Parallel Cache Assignment. In: : . Paper presented at 12th International Conference on Parallel Processing and Applied Mathematics (PPAM 2017).
Open this publication in new window or tab >>On the Tunability of a New Hessenberg Reduction Algorithm Using Parallel Cache Assignment
2017 (English)Conference paper, Published paper (Refereed)
National Category
Computer Sciences Computational Mathematics
Identifiers
urn:nbn:se:umu:diva-145342 (URN)
Conference
12th International Conference on Parallel Processing and Applied Mathematics (PPAM 2017)
Note

Accepted for publishing

Available from: 2018-02-28 Created: 2018-02-28 Last updated: 2018-06-09
Adlerborn, B., Kågström, B. & Karlsson, L. (2016). Distributed one-stage Hessenberg-triangular reduction with wavefront scheduling. Umeå: Department of Computing Science, Umeå University
Open this publication in new window or tab >>Distributed one-stage Hessenberg-triangular reduction with wavefront scheduling
2016 (English)Report (Other academic)
Abstract [en]

A novel parallel formulation of Hessenberg-triangular reduction of a regular matrix pair on distributed memory computers is presented. The formulation is based on a sequential cache-blocked algorithm by Kågstrom, Kressner, E.S. Quintana-Ortí, and G. Quintana-Ortí (2008). A static scheduling algorithm is proposed that addresses the problem of underutilized processes caused by two-sided updates of matrix pairs based on sequences of rotations. Experiments using up to 961 processes demonstrate that the new algorithm is an improvement of the state of the art but also identifies factors that currently limit its scalability.

Place, publisher, year, edition, pages
Umeå: Department of Computing Science, Umeå University, 2016. p. 26
Series
Report / UMINF, ISSN 0348-0542 ; 16.10
National Category
Computational Mathematics
Identifiers
urn:nbn:se:umu:diva-120002 (URN)
Available from: 2016-05-04 Created: 2016-05-04 Last updated: 2018-06-07Bibliographically approved
Eljammaly, M., Karlsson, L. & Kågström, B. (2016). Evaluation of the Tunability of a New NUMA-Aware Hessenberg Reduction Algorithm.
Open this publication in new window or tab >>Evaluation of the Tunability of a New NUMA-Aware Hessenberg Reduction Algorithm
2016 (English)Report (Other academic)
Series
Report / UMINF, ISSN 0348-0542 ; 16.21
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-152576 (URN)
Available from: 2018-10-14 Created: 2018-10-14 Last updated: 2018-10-14
Granat, R., Kagstrom, B., Kressner, D. & Shao, M. (2015). Algorithm 953: Parallel Library Software for the Multishift QR Algorithm with Aggressive Early Deflation. ACM Transactions on Mathematical Software, 41(4), Article ID 29.
Open this publication in new window or tab >>Algorithm 953: Parallel Library Software for the Multishift QR Algorithm with Aggressive Early Deflation
2015 (English)In: ACM Transactions on Mathematical Software, ISSN 0098-3500, E-ISSN 1557-7295, Vol. 41, no 4, article id 29Article in journal (Refereed) Published
Abstract [en]

Library software implementing a parallel small-bulge multishift QR algorithm with Aggressive Early Deflation (AED) targeting distributed memory high-performance computing systems is presented. Starting from recent developments of the parallel multishift QR algorithm [Granat et al., SIAM J. Sci. Comput. 32(4), 2010], we describe a number of algorithmic and implementation improvements. These include communication avoiding algorithms via data redistribution and a refined strategy for balancing between multishift QR sweeps and AED. Guidelines concerning several important tunable algorithmic parameters are provided. As a result of these improvements, a computational bottleneck within AED has been removed in the parallel multishift QR algorithm. A performance model is established to explain the scalability behavior of the new parallel multishift QR algorithm. Numerous computational experiments confirm that our new implementation significantly outperforms previous parallel implementations of the QR algorithm.

Keywords
Algorithms, Performance, Multishift QR algorithm, aggressive early deflation, parallel algorithms, stributed memory architectures
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-111765 (URN)10.1145/2699471 (DOI)000363733000007 ()2-s2.0-84943313977 (Scopus ID)
Available from: 2015-11-25 Created: 2015-11-23 Last updated: 2018-06-07Bibliographically approved
Dmytryshyn, A., Johansson, S. & Kågström, B. (2015). Canonical structure transitions of system pencils.
Open this publication in new window or tab >>Canonical structure transitions of system pencils
2015 (English)Report (Other academic)
Abstract [en]

We investigate the changes under small perturbations of the canonical structure information for a system pencil (A B C D) − s (E 0 0 0), det(E) ≠ 0, associated with a (generalized) linear time-invariant state-space system. The equivalence class of the pencil is taken with respect to feedback-injection equivalence transformation. The results allow to track possible changes under small perturbations of important linear system characteristics.

Publisher
p. 26
Series
Report / UMINF, ISSN 0348-0542 ; 15.15
Keywords
linear system, descriptor system, state-space system, system pencil, matrix pencil, orbit, bundle, perturbation, versal deformation, stratification
National Category
Mathematics Computer and Information Sciences Electrical Engineering, Electronic Engineering, Information Engineering Civil Engineering
Identifiers
urn:nbn:se:umu:diva-111632 (URN)
Funder
eSSENCE - An eScience CollaborationSwedish Research Council, E048530
Available from: 2015-11-18 Created: 2015-11-18 Last updated: 2018-06-07Bibliographically approved
Dmytryshyn, A., Futorny, V., Kågström, B., Klimenko, L. & Sergeichuk, V. (2015). Change of the congruence canonical form of 2-by-2 and 3-by-3 matrices under perturbations and bundles of matrices under congruence. Linear Algebra and its Applications, 469, 305-334
Open this publication in new window or tab >>Change of the congruence canonical form of 2-by-2 and 3-by-3 matrices under perturbations and bundles of matrices under congruence
Show others...
2015 (English)In: Linear Algebra and its Applications, ISSN 0024-3795, E-ISSN 1873-1856, Vol. 469, p. 305-334Article in journal (Refereed) Published
Abstract [en]

We construct the Hasse diagrams G2 and G3 for the closure ordering on the sets of congruence classes of 2 × 2 and 3 × 3 complex matrices. In other words, we construct two directed graphs whose vertices are 2 × 2 or, respectively, 3 × 3 canonical matrices under congruence, and there is a directed path from A to B if and only if A can be transformed by an arbitrarily small perturbation to a matrix that is congruent to B. A bundle of matrices under congruence is defined as a set of square matrices A for which the pencils A + λAT belong to the same bundle under strict equivalence. In support of this definition, we show that all matrices in a congruence bundle of 2 × 2 or 3 × 3 matrices have the same properties with respect to perturbations. We construct the Hasse diagrams G2 B and G3 B for the closure ordering on the sets of congruence bundles of 2 × 2 and, respectively, 3 × 3 matrices. We find the isometry groups of 2 × 2 and 3 × 3 congruence canonical matrices.

Keywords
Bundle, Closure graph, Congruence canonical form, Congruence class, Perturbation
National Category
Mathematics
Research subject
Mathematics; Computing Science
Identifiers
urn:nbn:se:umu:diva-101053 (URN)10.1016/j.laa.2014.11.004 (DOI)000348883600014 ()2-s2.0-84919935890 (Scopus ID)
Funder
eSSENCE - An eScience CollaborationSwedish Research Council, A0581501
Available from: 2015-03-18 Created: 2015-03-18 Last updated: 2018-06-07Bibliographically approved
Dmytryshyn, A. & Kågstrom, B. (2015). Coupled Sylvester-type Matrix Equations and Block Diagonalization. SIAM Journal on Matrix Analysis and Applications, 36(2), 580-593
Open this publication in new window or tab >>Coupled Sylvester-type Matrix Equations and Block Diagonalization
2015 (English)In: SIAM Journal on Matrix Analysis and Applications, ISSN 0895-4798, E-ISSN 1095-7162, Vol. 36, no 2, p. 580-593Article in journal (Refereed) Published
Abstract [en]

We prove Roth-type theorems for systems of matrix equations including an arbitrary mix of Sylvester and $\star$-Sylvester equations, in which the transpose or conjugate transpose of the unknown matrices also appear. In full generality, we derive consistency conditions by proving that such a system has a solution if and only if the associated set of $2 \times 2$ block matrix representations of the equations are block diagonalizable by (linked) equivalence transformations. Various applications leading to several particular cases have already been investigated in the literature, some recently and some long ago. Solvability of these cases follow immediately from our general consistency theory. We also show how to apply our main result to systems of Stein-type matrix equations.

Keywords
matrix equation, Sylvester equation, Stein equation, Roth's theorem, nsistency, block diagonalization, MMEL JW, 1987, LINEAR ALGEBRA AND ITS APPLICATIONS, V88-9, P139 anat R., 2007, BIT NUMERICAL MATHEMATICS, V47, P763
National Category
Computer Sciences Mathematical Analysis
Identifiers
urn:nbn:se:umu:diva-107104 (URN)10.1137/151005907 (DOI)000357407800011 ()
Available from: 2015-09-23 Created: 2015-08-18 Last updated: 2018-06-07Bibliographically approved
Organisations

Search in DiVA

Show all publications