1. |
- Arévalo, Carmen, et al.
(författare)
-
A software platform for adaptive high order multistep methods
- 2020
-
Ingår i: ACM Transactions on Mathematical Software. - : Association for Computing Machinery (ACM). - 0098-3500 .- 1557-7295. ; 46:1
-
Tidskriftsartikel (refereegranskat)abstract
- We present a software package, Modes, offering h-adaptive and p-adaptive linear multistep methods for first order initial value problems in ordinary differential equations. The implementation is based on a new parametric, grid-independent representation of multistep methods [Arévalo and Söderlind 2017]. Parameters are supplied for over 60 methods. For nonstiff problems, all maximal order methods (p=k for explicit and p=k+1 for implicit methods) are supported. For stiff computation, implicit methods of order p=k are included. A collection of step-size controllers based on digital filters is provided, generating smooth step-size sequences offering improved computational stability. Controllers may be selected to match method and problem classes. A new system for automatic order control is also provided for designated families of multistep methods, offering simultaneous h- and p-adaptivity. Implemented as a Matlab toolbox, the software covers high order computations with linear multistep methods within a unified, generic framework. Computational experiments show that the new software is competitive and offers qualitative improvements. Modes is available for downloading and is primarily intended as a platform for developing a new generation of state-of-the-art multistep solvers, as well as for true ceteris paribus evaluation of algorithmic components. This also enables method comparisons within a single implementation environment.
|
|
2. |
- Babuška, Ivo, et al.
(författare)
-
On roundoff error growth in elliptic problems
- 2018
-
Ingår i: ACM Transactions on Mathematical Software. - : Association for Computing Machinery (ACM). - 0098-3500 .- 1557-7295. ; 44:3
-
Tidskriftsartikel (refereegranskat)abstract
- Large-scale linear systems arise in finite-difference and finite-element discretizations of elliptic problems. With increasing computer performance, ever larger systems are solved using direct methods. How large can such systems be without roundoff compromising accuracy? Here we model roundoff dynamics in standard LU and LDLT decompositions with respect to problem size N. For the one-dimensional (1D) Poisson equation with Dirichlet boundary conditions on an equidistant grid, we show that the relative error in the factorized matrix grows like O(ϵN) if roundoffs are modeled as independent, expectation zero random variables. With bias, the growth rate changes to O(ϵN). Subsequent back substitution results in typical error growths of O(ϵNN) and O(ϵN2), respectively. Error growth is governed by the dynamics of the computational process and by the structure of the boundary conditions rather than by the condition number. Computational results are demonstrated in several examples, including a few fourth-order 1D problems and second-order 2D problems, showing that error accumulation depends strongly on the solution method. Thus, the same LU solver may exhibit different growth rates for the same 2D Poisson problem, depending on whether the five-point or nine-point FDM operator is used.
|
|
3. |
- Barthels, Henrik, et al.
(författare)
-
Linnea: Automatic Generation of Efficient Linear Algebra Programs
- 2021
-
Ingår i: ACM Transactions on Mathematical Software. - : ACM Digital Library. - 0098-3500 .- 1557-7295. ; 47:3
-
Tidskriftsartikel (refereegranskat)abstract
- The translation of linear algebra computations into efficient sequences of library calls is a non-trivial task that requires expertise in both linear algebra and high-performance computing. Almost all high-level languages and libraries for matrix computations (e.g., Matlab, Eigen) internally use optimized kernels such as those provided by BLAS and LAPACK; however, their translation algorithms are often too simplistic and thus lead to a suboptimal use of said kernels, resulting in significant performance losses. To combine the productivity offered by high-level languages, and the performance of low-level kernels, we are developing Linnea, a code generator for linear algebra problems. As input, Linnea takes a high-level description of a linear algebra problem; as output, it returns an efficient sequence of calls to high-performance kernels. Linnea uses a custom best-first search algorithm to find a first solution in less than a second, and increasingly better solutions when given more time. In 125 test problems, the code generated by Linnea almost always outperforms Matlab, Julia, Eigen, and Armadillo, with speedups up to and exceeding 10×.
|
|
4. |
|
|
5. |
- Bartlett, Roscoe A., et al.
(författare)
-
Hybrid differentiation strategies for simulation and analysis of applications in C+
- 2008
-
Ingår i: ACM Transactions on Mathematical Software. - : Association for Computing Machinery (ACM). - 0098-3500 .- 1557-7295. ; 35:1, s. 1:1-29
-
Tidskriftsartikel (refereegranskat)abstract
- Computationally efficient and accurate derivatives are important to the success of many different types of numerical methods. Automatic differentation (AD) approaches compute truncation-free derivatives and can be efficient in many cases. Although present AD tools can provide a convenient implementation mechanism, the computational efficiency rarely compares to analytically derived versions that have been carefully implemented. The focus of this work is to combine the strength of these methods into a hybrid strategy that attempts to achieve an optimal balance of implementation and computational efficiency by selecting the appropriate components of the target algorithms for AD and analytical derivation. Although several AD approaches can be considered, our focus is on the use of template overloading forward AD tools in C++ applications. We demonstrate this hybrid strategy for a system of partial differential equations in gas dynamics. These methods apply however to other systems of differentiable equations, including DAEs and ODEs.
|
|
6. |
- Brust, Johannes, et al.
(författare)
-
Algorithm 1030: SC-SR1: MATLAB Software for Limited-memory SR1 Trust-region Methods
- 2022
-
Ingår i: ACM Transactions on Mathematical Software. - : ASSOC COMPUTING MACHINERY. - 0098-3500 .- 1557-7295. ; 48:4
-
Tidskriftsartikel (refereegranskat)abstract
- We present a MATLAB implementation of the symmetric rank-one (SC-SR1) method that solves trust-region subproblems when a limited-memory symmetric rank-one (L-SR1) matrix is used in place of the true Hessian matrix, which can be used for large-scale optimization. The method takes advantage of two shape-changing norms [Burdakov et al. 2017; Burdakov and Yuan 2002] to decompose the trust-region subproblem into two separate problems. Using one of the proposed norms, the resulting subproblems have closed-form solutions. Meanwhile, using the other proposed norm, one of the resulting subproblems has a closed-form solutionwhile the other is easily solvable using techniques that exploit the structure of L-SR1 matrices. Numerical results suggest that the SC-SR1 method is able to solve trust-region subproblems to high accuracy even in the so-called "hard case." When integrated into a trust-region algorithm, extensive numerical experiments suggest that the proposed algorithms perform well, when compared with widely used solvers, such as truncated conjugate-gradients.
|
|
7. |
- Edlund, Ove
(författare)
-
A software package for sparse orthogonal factorization and updating
- 2002
-
Ingår i: ACM Transactions on Mathematical Software. - : Association for Computing Machinery (ACM). - 0098-3500 .- 1557-7295. ; 28:4, s. 448-482
-
Tidskriftsartikel (refereegranskat)abstract
- Although there is good software for sparse QR factorization, there is little support for updating and downdating, something that is absolutely essential in some linear programming algorithms, for example. This article describes an implementation of sparse LQ factorization, including block triangularization, approximate minimum degree ordering, symbolic factorization, multifrontal factorization, and updating and downdating. The factor Q is not retained. The updating algorithm expands the nonzero pattern of the factor L, which is reflected in the dynamic representation of L. The block triangularization is used as an `ordering for sparsity' rather than as a prerequisite for block backward substitution. In symbolic factorization, something called `element counters' is introduced to reduce the overestimation of the number of nonzeros that the commonly used methods do. Both the approximate minimum degree ordering and the symbolic factorization are done without explicitly forming the nonzero pattern of the symmetric matrix in the corresponding normal equations. Tests show that the average time used for a single update or downdate is essentially the same as the time used for a single forward or backward substitution. Other parts of the implementation show the same range of performance as existing code, but cannot be replaced because of the special character of the systems that are solved.
|
|
8. |
- Granat, Robert, et al.
(författare)
-
Algorithm 953 : Parallel Library Software for the Multishift QR Algorithm with Aggressive Early Deflation
- 2015
-
Ingår i: ACM Transactions on Mathematical Software. - : Association for Computing Machinery (ACM). - 0098-3500 .- 1557-7295. ; 41:4
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
9. |
|
|
10. |
- Granat, Robert, et al.
(författare)
-
Parallel Solvers for Sylvester-type Matrix Equations with Applications in Condition Estimation, Part I : Theory and Algorithms
- 2010
-
Ingår i: ACM Transactions on Mathematical Software. - New York : ACM Press. - 0098-3500 .- 1557-7295. ; 37:3, s. 32:1-32:32
-
Tidskriftsartikel (refereegranskat)abstract
- Parallel ScaLAPACK-style algorithms for solving eight common standard and generalized Sylvester-type matrix equations and various sign and transposed variants are presented. All algorithms are blocked variants based on the Bartels--Stewart method and involve four major steps: reduction to triangular form, updating the right-hand side with respect to the reduction, computing the solution to the reduced triangular problem, and transforming the solution back to the original coordinate system. Novel parallel algorithms for solving reduced triangular matrix equations based on wavefront-like traversal of the right-hand side matrices are presented together with a generic scalability analysis. These algorithms are used in condition estimation and new robust parallel sep − 1-estimators are developed. Experimental results from three parallel platforms, including results from a mixed OpenMP/MPI platform, are presented and analyzed using several performance and accuracy metrics. The analysis includes results regarding general and triangular parallel solvers as well as parallel condition estimators.
|
|