| 1. |
- Alnaes, Martin, et al.
(författare)
-
Unified Form Language: A Domain-Specific Language for Weak Formulations of Partial Differential Equations
- 2014
-
Ingår i: ACM Transactions on Mathematical Software. - 0098-3500. ; 40:2, s. artikel nr 9-
-
Tidskriftsartikel (refereegranskat)abstract
- We present the Unified Form Language (UFL), which is a domain-specific language for representing weak formulations of partial differential equations with a view to numerical approximation. Features of UFL include support for variational forms and functionals, automatic differentiation of forms and expressions, arbitrary function space hierarchies for multifield problems, general differential operators and flexible tensor algebra. With these features, UFL has been used to effortlessly express finite element methods for complex systems of partial differential equations in near-mathematical notation, resulting in compact, intuitive and readable programs. We present in this work the language and its construction. An implementation of UFL is freely available as an open-source software library. The library generates abstract syntax tree representations of variational problems, which are used by other software libraries to generate concrete low-level implementations. Some application examples are presented and libraries that support UFL are highlighted.
|
|
| 2. |
- 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.
|
|
| 3. |
- 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.
|
|
| 4. |
- 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×.
|
|
| 5. |
|
|
| 6. |
- 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.
|
|
| 7. |
- 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.
|
|
| 8. |
- 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.
|
|
| 9. |
- 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.
|
|
| 10. |
|
|
