Program

Modular and adaptive mixed precision algorithms

Modern computer hardware supports an increasingly wide range of arithmetics, notably low precision floating-point ones. Lower precisions provide significant storage, communication, speed, and energy benefits that make them very attractive for high performance computing. However, they also provide a correspondingly lower accuracy. This motivates the development of mixed precision algorithms, which combine multiple precisions to achieve both high performance and high accuracy. In this talk, I will present two emerging trends in the design of mixed precision algorithms that have significant potential: modularity and adaptivity. Modularity allows for easily deriving stable mixed precision variants of an algorithm and for combining them with other types of approximations. Adaptivity allows for dynamically taking advantage of application-specific opportunities by switching the least sensitive parts of the data to low precision.

Mixed Precision Training of Gaussian Processes

Gaussian processes are one of the most popular tools in scientific computing. Depending on the application, different kernel functions and their gradients can be used. Computing the gradient of the kernel matrix can be computationally very expensive and may exceed the memory limit. Due to matrix and vector operations, gradient calculation dominates the cost of the whole algorithm depending on the size of the dataset. There are various techniques currently being used in Gaussian processes to avoid memory and cost-related problems, such as low-rank approximation and using matrix determinant lemma. Another technique can be using multiple precisions in the training algorithm. When the data is large, one may not need a high accuracy for training. Low precision is thus commonly used in data science applications. However, using lower precision can introduce stability issues in direct or iterative solvers used in the training algorithm. Thus, one must use a higher precision in such parts of the algorithm without sacrificing the performance. In this talk, we introduce a new mixed-precision approach to train Gaussian processes using several techniques. Motivated by the recent emergence of commercially available low-precision hardware, we propose to use multiple precisions during training, low-rank approximation, and a stable direct solver to have a cheap, fast, and stable algorithm.

Sketching a symmetric positive semidefinite matrix in low precision

A single-pass Nyström method can be used to approximate a symmetric positive semidefinite matrix A when computations with it are expensive. In this talk, we consider a two precision variant of the method, where the expensive sketching step is assumed to be performed in the lower of the two precisions. We discuss when the use of low precision does not affect the accuracy of the approximation, and show that this approximation can be used to construct a specific preconditioner for the conjugate gradient method.

A multilinear Nyström algorithm for low-rank approximation of tensors in Tucker format

The Nyström method offers an effective way to obtain low-rank approximation of SPD matrices, and has been recently extended and analyzed to nonsymmetric matrices (leading to the randomized, single-pass, streamable, cost-effective, and accurate alternative to the randomized SVD, and it facilitates the computation of several matrix low-rank factorizations. In this presentation, we take these advancements a step further by introducing a higher-order variant of Nyström's methodology tailored to approximating low-rank tensors in the Tucker format: the multilinear Nyström technique. We show that, by introducing appropriate small modifications in the formulation of the higher-order method, strong stability properties can be obtained. This algorithm retains the key attributes of the generalized Nyström method, positioning it as a viable substitute for the randomized higher-order SVD algorithm.

Randomized low-rank approximation of parameter-dependent matrices

Randomized algorithms are an increasingly popular approach for performing low-rank approximation and they usually proceed by multiplying the matrix with random dimension reduction matrices (DRMs). Applying such algorithms directly to a matrix A(t) depending on a parameter t in a compact set D of R^d would involve multiplying different, independent DRMs for every t, which is not only expensive but also leads to inherently non-smooth approximations. In this talk, we propose to use constant DRMs, that is, A(t) is multiplied with the same DRM for every t. The resulting parameter-dependent extensions of two popular randomized algorithms, the randomized singular value decomposition and the generalized Nyström method, are computationally attractive. Therefore, we provide a probabilistic analysis for both algorithms when using Gaussian random DRMs, it shows that our methods reliably return quasi-best low-rank approximations.

Randomization techniques for solving linear systems of equations and eigenvalue problems

In this talk we discuss recent progress in using randomization for solving linear systems of equations and eigenvalue problems. We present first randomized versions of processes for orthogonalizing a set of vectors and their usage in the Arnoldi iteration. We then present associated Krylov subspace methods for solving large scale linear systems of equations and eigenvalue problems. The new methods retain the numerical stability of classic Krylov methods while reducing communication and being more efficient on modern massively parallel computers.

A sketch-and-select Arnoldi process

In recent literature, sketching has been used to improve Krylov subspace methods for several linear algebra tasks, such as the solution of linear systems or eigenvalue problems. By solving a sketched version of the problem projected on the Krylov subspace, the solution of the original problem can be efficiently approximated even when the Krylov subspace basis is not orthonormal. This makes it possible to reduce orthogonalization costs in the basis construction procedure by replacing the standard Arnoldi algorithm with the k-truncated Arnoldi algorithm, where each vector is orthogonalized only against the last k basis vectors, for a (small) fixed integer k. In this talk we propose a sketch-and-select Arnoldi process that, at each iteration, utilizes sketching to select k of the previously computed basis vectors to project out of the current basis vector. This procedure has a computational cost that is comparable to the cost of truncated Arnoldi, but very often it produces a basis with a smaller condition number. The subset selection problem is approximately solved using a number of different heuristic algorithms, and the most effective ones are identified using performance profiles. The applicability of the proposed sketch-and-select Arnoldi process is evaluated by using it as a basis constructor within sketched GMRES.
This is a joint work with Stefan Güttel.
This activity is performed in the framework of the PRIN 2022 project "Low-rank Structures and Numerical Methods in Matrix and Tensor Computations and their Application".

Sketched and truncated Krylov subspace methods for matrix equations

Sketching can be seen as a randomized dimensionality reduction technique able to preserve the main features of the original problem with probabilistic confidence.
This kind of technique is emerging as one of the most promising tools to boost numerical computations and it is quite well-known by theoretical computer scientists.
Nowadays, sketching is gaining popularity also in the numerical linear algebra community even though its use and understanding are still limited.
In this talk we will present cutting-edge results about the use of sketching in numerical linear algebra. In particular, we will focus on showing how sketching can be successfully combined with Krylov subspace methods. We will specialize our results to the solution of large-scale matrix equations but similar techniques can be applied to a variety of important algebraic problems, including the solution of linear systems, eigenvalue problems, and the numerical evaluation of matrix functions.
This talk is based upon joint work with Valeria Simoncini and Marcel Schweitzer.