Umeå University's logo

umu.sePublications
Change search
Link to record
Permanent link

Direct link
Kjelgaard Mikkelsen, Carl ChristianORCID iD iconorcid.org/0000-0002-9158-1941
Publications (10 of 28) Show all publications
López-Villellas, L., Kjelgaard Mikkelsen, C. C., Galano-Frutos, J. J., Marco-Sola, S., Alastruey-Benedé, J., Ibáñez, P., . . . García-Risueño, P. (2023). Accurate and efficient constrained molecular dynamics of polymers using Newton's method and special purpose code. Computer Physics Communications, 288, Article ID 108742.
Open this publication in new window or tab >>Accurate and efficient constrained molecular dynamics of polymers using Newton's method and special purpose code
Show others...
2023 (English)In: Computer Physics Communications, ISSN 0010-4655, E-ISSN 1879-2944, Vol. 288, article id 108742Article in journal (Refereed) Published
Abstract [en]

In molecular dynamics simulations we can often increase the time step by imposing constraints on bond lengths and bond angles. This allows us to extend the length of the time interval and therefore the range of physical phenomena that we can afford to simulate. We examine the existing algorithms and software for solving nonlinear constraint equations in parallel and we explain why it is necessary to advance the state-of-the-art. We present ILVES-PC, a new algorithm for imposing bond constraints on proteins accurately and efficiently. It solves the same system of differential algebraic equations as the celebrated SHAKE algorithm, but ILVES-PC solves the nonlinear constraint equations using Newton’s method rather than the nonlinear Gauss-Seidel method. Moreover, ILVES-PC solves the necessary linear systems using a specialized linear solver that exploits the structure of the protein. ILVES-PC can rapidly solve constraint equations as accurately as the hardware will allow. The run-time of ILVES-PC is proportional to the number of constraints. We have integrated ILVES-PC into GROMACS and simulated proteins of different sizes. Compared with SHAKE, we have achieved speedups of up to 4.9× in single-threaded executions and up to 76× in shared-memory multi-threaded executions. Moreover, ILVES-PC is more accurate than P-LINCS algorithm. Our work is a proof-of-concept of the utility of software designed specifically for the simulation of polymers.

Place, publisher, year, edition, pages
Elsevier, 2023
Keywords
molecular dynamics, constraint algorithms, nonlinear equations, newton's method, SHAKE, LINCS
National Category
Computational Mathematics
Identifiers
urn:nbn:se:umu:diva-208209 (URN)10.1016/j.cpc.2023.108742 (DOI)2-s2.0-85151493578 (Scopus ID)
Funder
Swedish Research CouncileSSENCE - An eScience Collaboration
Available from: 2023-05-11 Created: 2023-05-11 Last updated: 2023-05-11Bibliographically approved
Kjelgaard Mikkelsen, C. C., López-Villellas, L. & García-Risueño, P. (2023). How accurate does Newton have to be?. In: Roman Wyrzykowski; Jack Dongarra; Ewa Deelman; Konrad Karczewski (Ed.), Roman Wyrzykowski et. al. (Ed.), Parallel processing and applied mathematics: 14th International conference, PPAM 2022, Gdansk, Poland, September 11–14, 2022, revised selected papers, part I. Paper presented at PPAM 2022 (pp. 3-15). Paper presented at PPAM 2022. Switzerland: Springer Nature, 1
Open this publication in new window or tab >>How accurate does Newton have to be?
2023 (English)In: Parallel processing and applied mathematics: 14th International conference, PPAM 2022, Gdansk, Poland, September 11–14, 2022, revised selected papers, part I / [ed] Roman Wyrzykowski; Jack Dongarra; Ewa Deelman; Konrad Karczewski, Switzerland: Springer Nature, 2023, Vol. 1, p. 3-15Chapter in book (Refereed)
Abstract [en]

We analyze the convergence of quasi-Newton methods in exact and finite precision arithmetic. In particular, we derive an upper bound for the stagnation level and we show that any sufficiently exact quasi-Newton method will converge quadratically until stagnation. In the absence of sufficient accuracy, we are likely to retain rapid linear convergence. We confirm our analysis by computing square roots and solving bond constraint equations in the context of molecular dynamics. We briefly discuss implications for parallel solvers.

Place, publisher, year, edition, pages
Switzerland: Springer Nature, 2023
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 13826
Keywords
systems of nonlinear equations, quasi-Newton methods, approxomation error, rounding error, convergence, stagnation
National Category
Computational Mathematics
Identifiers
urn:nbn:se:umu:diva-208210 (URN)10.1007/978-3-031-30442-2_1 (DOI)2-s2.0-85161395821 (Scopus ID)978-3-031-30441-5 (ISBN)978-3-031-30442-2 (ISBN)
Conference
PPAM 2022
Funder
eSSENCE - An eScience Collaboration
Available from: 2023-05-11 Created: 2023-05-11 Last updated: 2023-06-28Bibliographically approved
Kjelgaard Mikkelsen, C. C., López-Villellas, L. & García-Risueño, P. (2023). Newton's method revisited: how accurate do we have to be?. Concurrency and Computation
Open this publication in new window or tab >>Newton's method revisited: how accurate do we have to be?
2023 (English)In: Concurrency and Computation, ISSN 1532-0626, E-ISSN 1532-0634Article in journal (Refereed) Epub ahead of print
Abstract [en]

We analyze the convergence of quasi-Newton methods in exact and finite precision arithmetic using three different techniques. We derive an upper bound for the stagnation level and we show that any sufficiently exact quasi-Newton method will converge quadratically until stagnation. In the absence of sufficient accuracy, we are likely to retain rapid linear convergence. We confirm our analysis by computing square roots and solving bond constraint equations in the context of molecular dynamics. In particular, we apply both a symmetric variant and Forsgren's variant of the simplified Newton method. This work has implications for the implementation of quasi-Newton methods regardless of the scale of the calculation or the machine.

Place, publisher, year, edition, pages
John Wiley & Sons, 2023
Keywords
approximation error, convergence, quasi-Newton methods, rounding error, stagnation, systems of nonlinear equations
National Category
Computational Mathematics
Identifiers
urn:nbn:se:umu:diva-212265 (URN)10.1002/cpe.7853 (DOI)001020863100001 ()2-s2.0-85164157230 (Scopus ID)
Available from: 2023-07-20 Created: 2023-07-20 Last updated: 2023-09-05
Myllykoski, M. & Kjelgaard Mikkelsen, C. C. (2021). Task‐based, GPU‐accelerated and robust library for solving dense nonsymmetric eigenvalue problems. Concurrency and Computation, 33(11), Article ID e5915.
Open this publication in new window or tab >>Task‐based, GPU‐accelerated and robust library for solving dense nonsymmetric eigenvalue problems
2021 (English)In: Concurrency and Computation, ISSN 1532-0626, E-ISSN 1532-0634, Vol. 33, no 11, article id e5915Article in journal (Refereed) Published
Abstract [en]

In this paper, we present the StarNEig library for solving dense nonsymmetric standard and generalized eigenvalue problems. The library is built on top of the StarPU runtime system and targets both shared and distributed memory machines. Some components of the library have support for GPU acceleration. The library currently applies to real matrices with real and complex eigenvalues and all calculations are done using real arithmetic. Support for complex matrices is planned for a future release. This paper is aimed at potential users of the library. We describe the design choices and capabilities of the library, and contrast them to existing software such as LAPACK and ScaLAPACK. StarNEig implements a ScaLAPACK compatibility layer which should assist new users in the transition to StarNEig. We demonstrate the performance of the library with a sample of computational experiments.

Place, publisher, year, edition, pages
John Wiley & Sons, 2021
Keywords
eigenvalue problem, parallel computing, task‐based, numerical library
National Category
Computer Sciences Computational Mathematics
Research subject
Computer Science
Identifiers
urn:nbn:se:umu:diva-173924 (URN)10.1002/cpe.5915 (DOI)000555868500001 ()2-s2.0-85089025359 (Scopus ID)
Projects
NLAFET
Available from: 2020-08-06 Created: 2020-08-06 Last updated: 2021-07-14Bibliographically approved
Myllykoski, M. & Kjelgaard Mikkelsen, C. C. (2020). Introduction to StarNEig: A Task-based Library for Solving Nonsymmetric Eigenvalue Problems. In: Roman Wyrzykowski and Boleslaw Szymanski (Ed.), Parallel Processing and Applied Mathematics: Revised Selected Papers, Part I. Paper presented at 13th International Conference on Parallel Computing and Applied Mathematics, PPAM 2019, Bialystok, Poland, September 8-11, 2019 (pp. 70-81). Springer
Open this publication in new window or tab >>Introduction to StarNEig: A Task-based Library for Solving Nonsymmetric Eigenvalue Problems
2020 (English)In: Parallel Processing and Applied Mathematics: Revised Selected Papers, Part I / [ed] Roman Wyrzykowski and Boleslaw Szymanski, Springer, 2020, p. 70-81Conference paper, Published paper (Refereed)
Abstract [en]

Abstract. In this paper, we present the StarNEig library for solvingdense nonsymmetric (generalized) eigenvalue problems. The library isbuilt on top of the StarPU runtime system and targets both shared anddistributed memory machines. Some components of the library supportGPUs. The library is currently in an early beta state and only real arith-metic is supported. Support for complex data types is planned for afuture release. This paper is aimed at potential users of the library. Wedescribe the design choices and capabilities of the library, and contrastthem to existing software such as ScaLAPACK. StarNEig implements aScaLAPACK compatibility layer that should make it easy for new usersto transition to StarNEig. We demonstrate the performance of the librarywith a small set of computational experiments.

Place, publisher, year, edition, pages
Springer, 2020
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 12043
Keywords
Eigenvalue problem, Task-based, Library
National Category
Computer Sciences
Research subject
Computer Science; Mathematics
Identifiers
urn:nbn:se:umu:diva-168419 (URN)10.1007/978-3-030-43229-4_7 (DOI)2-s2.0-85083964403 (Scopus ID)978-3-030-43228-7 (ISBN)978-3-030-43229-4 (ISBN)
Conference
13th International Conference on Parallel Computing and Applied Mathematics, PPAM 2019, Bialystok, Poland, September 8-11, 2019
Projects
NLAFET
Available from: 2020-02-25 Created: 2020-02-25 Last updated: 2023-03-23Bibliographically approved
Kjelgaard Mikkelsen, C. C. & Myllykoski, M. (2020). Parallel Robust Computation of Generalized Eigenvectors of Matrix Pencils. In: Roman Wyrzykowski, Ewa Deelman, Jack Dongarra, Konrad Karczewski (Ed.), Parallel Processing and Applied Mathematics: Revised Selected Papers, Part I. Paper presented at 13th International Conference on Parallel Processing and Applied Mathematics, PPAM 2019, Bialystok, Poland, September 8-11, 2019 (pp. 58-69). Springer
Open this publication in new window or tab >>Parallel Robust Computation of Generalized Eigenvectors of Matrix Pencils
2020 (English)In: Parallel Processing and Applied Mathematics: Revised Selected Papers, Part I / [ed] Roman Wyrzykowski, Ewa Deelman, Jack Dongarra, Konrad Karczewski, Springer, 2020, p. 58-69Conference paper, Published paper (Refereed)
Abstract [en]

In this paper we consider the problem of computing generalized eigenvectors of a matrix pencil in real Schur form. In exact arithmetic, this problem can be solved using substitution. In practice, substitution is vulnerable to floating-point overflow. The robust solvers xtgevc in LAPACK prevent overflow by dynamically scaling the eigenvectors.These subroutines are scalar and sequential codes which compute theeigenvectors one by one. In this paper, we discuss how to derive robust algorithms which are blocked and parallel. The new StarNEig librarycontains a robust task-parallel solver Zazamoukh which runs on top of StarPU. Our numerical experiments show that Zazamoukh achieves a super-linear speedup compared with dtgevc for sufficiently large matrices.

Place, publisher, year, edition, pages
Springer, 2020
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 12043
Keywords
Generalized eigenvectors, overflow protection, task-parallelism
National Category
Computer Sciences
Research subject
Computer Science; Mathematics
Identifiers
urn:nbn:se:umu:diva-168416 (URN)10.1007/978-3-030-43229-4_6 (DOI)2-s2.0-85083956421 (Scopus ID)978-3-030-43228-7 (ISBN)978-3-030-43229-4 (ISBN)
Conference
13th International Conference on Parallel Processing and Applied Mathematics, PPAM 2019, Bialystok, Poland, September 8-11, 2019
Projects
NLAFET
Available from: 2020-02-25 Created: 2020-02-25 Last updated: 2023-03-24Bibliographically approved
Schwarz, A. B., Kjelgaard Mikkelsen, C. C. & Karlsson, L. (2020). Robust Parallel Eigenvector Computation for the Non-Symmetric Eigenvalue Problem. Umeå universitet
Open this publication in new window or tab >>Robust Parallel Eigenvector Computation for the Non-Symmetric Eigenvalue Problem
2020 (English)Report (Other academic)
Abstract [en]

A standard approach for computing eigenvectors of a non-symmetric matrix reduced to real Schurform 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.

Place, publisher, year, edition, pages
Umeå universitet, 2020. p. 25
Series
Report / UMINF, ISSN 0348-0542 ; 20.02
National Category
Computer Sciences
Research subject
Computer Science; Mathematics
Identifiers
urn:nbn:se:umu:diva-168433 (URN)
Projects
NLAFET
Available from: 2020-02-25 Created: 2020-02-25 Last updated: 2023-03-07Bibliographically approved
Schwarz, A. B., Kjelgaard Mikkelsen, C. C. & Karlsson, L. (2020). Robust parallel eigenvector computation for the non-symmetric eigenvalue problem. Parallel Computing, 100, Article ID 102707.
Open this publication in new window or tab >>Robust parallel eigenvector computation for the non-symmetric eigenvalue problem
2020 (English)In: Parallel Computing, ISSN 0167-8191, E-ISSN 1872-7336, Vol. 100, article id 102707Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Elsevier, 2020
Keywords
Overflow protection, Eigenvectors, Real Schur form, Tiled algorithms
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:umu:diva-177534 (URN)10.1016/j.parco.2020.102707 (DOI)000597159800001 ()2-s2.0-85089018373 (Scopus ID)
Projects
NLAFET
Note

Preprint version: http://umu.diva-portal.org/smash/record.jsf?pid=diva2%3A1396196&dswid=-7045

Available from: 2020-12-11 Created: 2020-12-11 Last updated: 2023-03-24Bibliographically approved
Schwarz, A. B. & Kjelgaard Mikkelsen, C. C. (2020). Robust Task-Parallel Solution of the Triangular Sylvester Equation. In: Roman Wyrzykowski, Ewa Deelman, Jack Dongarra, Konrad Karczewski (Ed.), Parallel Processing and Applied Mathematics: 13th International Conference, PPAM 2019, Bialystok, Poland, September 8–11, 2019, Revised Selected Papers, Part I. Paper presented at 13th International Conference, PPAM 2019, Bialystok, Poland, September 8–11, 2019 (pp. 82-92). Springer
Open this publication in new window or tab >>Robust Task-Parallel Solution of the Triangular Sylvester Equation
2020 (English)In: Parallel Processing and Applied Mathematics: 13th International Conference, PPAM 2019, Bialystok, Poland, September 8–11, 2019, Revised Selected Papers, Part I / [ed] Roman Wyrzykowski, Ewa Deelman, Jack Dongarra, Konrad Karczewski, Springer, 2020, p. 82-92Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Springer, 2020
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 12043
Keywords
Overflow protection, Task parallelism, Triangular Sylvester equation, Real Schur form
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:umu:diva-159435 (URN)10.1007/978-3-030-43229-4_8 (DOI)2-s2.0-85084010959 (Scopus ID)978-3-030-43228-7 (ISBN)978-3-030-43229-4 (ISBN)
Conference
13th International Conference, PPAM 2019, Bialystok, Poland, September 8–11, 2019
Funder
EU, Horizon 2020, 671633
Note

Originally included in thesis in manuscript form. 

Preprint version: https://arxiv.org/abs/1905.10574

Available from: 2019-05-28 Created: 2019-05-28 Last updated: 2023-03-23Bibliographically approved
Myllykoski, M., Kjelgaard Mikkelsen, C. C., Schwarz, A. B. & Kågström, B. (2019). D2.7 Eigenvalue solvers for nonsymmetric problems. NLAFET Consortium; Umeå University
Open this publication in new window or tab >>D2.7 Eigenvalue solvers for nonsymmetric problems
2019 (English)Report (Other academic)
Place, publisher, year, edition, pages
NLAFET Consortium; Umeå University, 2019. p. 29
National Category
Computer Sciences
Research subject
Mathematics; Computer Science
Identifiers
urn:nbn:se:umu:diva-168424 (URN)
Projects
NLAFET
Note

This work is c by the NLAFET Consortium, 2015–2019. Its duplication is allowed only for personal, educational, or research uses.

Available from: 2020-02-25 Created: 2020-02-25 Last updated: 2023-03-07Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-9158-1941

Search in DiVA

Show all publications