Search

The sparse matrix-vector (SpMV) multiplication is an important computational kernel, but it is notoriously difficult to execute efficiently. This paper investigates algorithm performance for unstructured sparse matrices, which are more common than ever because of the trend towards large-scale data collection. The development of an SpMV multiplication algorithm for this type of data is hard due to two factors. First, parallel load balancing issues arise because of the unpredictable nonzero structure. Secondly, SpMV multiplication algorithms are inevitably memory-bound because the sparsity causes a low arithmetic intensity. Three state-of-the-art algorithms for parallel SpMV multiplication on shared-memory systems are discussed. Six new hybrid algorithms are developed which combine optimization techniques of the current algorithms. These techniques include parallelization strategies, storage formats, and nonzero orderings. A modern and high-performance implementation of all discussed algorithms is provided as open-source software. Using this implementation the algorithms are compared. Furthermore, SpMV multiplication algorithms require the matrix to be stored in a specific storage format. Therefore, the conversion time between these storage formats is also analyzed. Both tests are performed for multiple unstructured sparse matrices on different machines: two multi-CPU and two single-CPU architectures. We show that one of the newly developed algorithms outperforms the current state-of-the-art by 19% on one of the multi-CPU architectures. When taking conversion time into consideration, we show that 472 SpMV multiplications are needed to cover the cost of converting to a new storage format for one of the hybrid algorithms on a multi-CPU machine.

Recently, the ParaOpt algorithm was proposed as an extension of the time-parallel Parareal method to optimal control. ParaOpt uses quasi-Newton steps that each require solving a system of matching conditions iteratively. The state-of-the-art parallel preconditioner for linear problems leads to a set of independent smaller systems that are currently hard to solve. We generalize the preconditioner to the nonlinear case and propose a new, fast inversion method for these smaller systems, avoiding disadvantages of the current options with adjusted boundary conditions in the subproblems.

The numerical solution of singular generalized eigenvalue problems is still challenging. In Hochstenbach, Mehl, and Plestenjak, Solving Singular Generalized Eigenvalue Problems by a Rank-Completing Perturbation, SIMAX 2019, a rank-completing perturbation was proposed and a related bordering of the singular pencil. For large sparse pencils, we propose an LU factorization that determines a rank completing perturbation that regularizes the pencil and that is then used in the shift-and-invert Arnoldi method to obtain eigenvalues nearest a shift. Numerical examples illustrate the theory and the algorithms.

Boundary integral equation formulations of elliptic partial differential equations lead to dense system matrices when discretized, yet they are data-sparse. Using the $\mathcal{H}$-matrix format, this sparsity is exploited to achieve $\mathcal{O}(N\log N)$ complexity for storage and multiplication by a vector. This is achieved purely algebraically, based on low-rank approximations of subblocks, and hence the format is also applicable to a wider range of problems. The $\mathcal{H}^2$-matrix format improves the complexity to $\mathcal{O}(N)$ by introducing a recursive structure onto subblocks on multiple levels. However, in practice this comes with a large proportionality constant, making the $\mathcal{H}^2$-matrix format advantageous mostly for large problems. In this paper we investigate the usefulness of a matrix format that lies in between these two: Uniform $\mathcal{H}$-matrices. An algebraic compression algorithm is introduced to transform a regular $\mathcal{H}$-matrix into a uniform $\mathcal{H}$-matrix, which maintains the asymptotic complexity.

In this article a fast and parallelizable algorithm for rational approximation is presented. The method, called (P)QR-AAA, is a (parallel) set-valued variant of the AAA algorithm for scalar functions. It builds on the set-valued AAA framework introduced by Lietaert, Meerbergen, P{\'e}rez and Vandereycken, accelerating it by using an approximate orthogonal basis obtained from a truncated QR decomposition. We demonstrate both theoretically and numerically this method's accuracy and efficiency. We show how it can be parallelized while maintaining the desired accuracy, with minimal communication cost.

The ParaOpt algorithm was recently introduced as a time-parallel solver for optimal-control problems with a terminal-cost objective, and convergence results have been presented for the linear diffusive case with implicit-Euler time integrators. We reformulate ParaOpt for tracking problems and provide generalized convergence analyses for both objectives. We focus on linear diffusive equations and prove convergence bounds that are generic in the time integrators used. For large problem dimensions, ParaOpt's performance depends crucially on having a good preconditioner to solve the arising linear systems. For the case where ParaOpt's cheap, coarse-grained propagator is linear, we introduce diagonalization-based preconditioners inspired by recent advances in the ParaDiag family of methods. These preconditioners not only lead to a weakly-scalable ParaOpt version, but are themselves invertible in parallel, making maximal use of available concurrency. They have proven convergence properties in the linear diffusive case that are generic in the time discretization used, similarly to our ParaOpt results. Numerical results confirm that the iteration count of the iterative solvers used for ParaOpt's linear systems becomes constant in the limit of an increasing processor count. The paper is accompanied by a sequential MATLAB implementation.

The ParaDiag family of algorithms solves differential equations by using preconditioners that can be inverted in parallel through diagonalization. In the context of optimal control of linear parabolic PDEs, the state-of-the-art ParaDiag method is limited to solving self-adjoint problems with a tracking objective. We propose three improvements to the ParaDiag method: the use of alpha-circulant matrices to construct an alternative preconditioner, a generalization of the algorithm for solving non-self-adjoint equations, and the formulation of an algorithm for terminal-cost objectives. We present novel analytic results about the eigenvalues of the preconditioned systems for all discussed ParaDiag algorithms in the case of self-adjoint equations, which proves the favorable properties the alpha-circulant preconditioner. We use these results to perform a theoretical parallel-scaling analysis of ParaDiag for self-adjoint problems. Numerical tests confirm our findings and suggest that the self-adjoint behavior, which is backed by theory, generalizes to the non-self-adjoint case. We provide a sequential, open-source reference solver in Matlab for all discussed algorithms.

The analysis of sound and vibrations is often performed in the frequency domain, implying the assumption of steady-state behaviour and time-harmonic excitation. External excitations, however, may be transient rather than time-harmonic, requiring time-domain analysis. Some material properties, e.g.\ often used to represent for damping treatments, are still described in the frequency domain, which complicates simulation in time. In this paper, we present a method for the linearization of finite element models with nonlinear frequency dependencies. The linearization relies on the rational approximation of the finite element matrices by the AAA method. We introduce the Extended AAA method, which is classical AAA combined with a degree two polynomial term to capture the second order behaviour of the models. A filtering step is added for removing unstable poles.

Solving polynomial eigenvalue problems with eigenvector nonlinearities (PEPv) is an interesting computational challenge, outside the reach of the well-developed methods for nonlinear eigenvalue problems. We present a natural generalization of these methods which leads to a contour integration approach for computing all eigenvalues of a PEPv in a compact region of the complex plane. Our methods can be used to solve any suitably generic system of polynomial or rational function equations., Comment: 24 pages, 6 figures

We present a method to linearize, without approximation, a specific class of eigenvalue problems with eigenvector nonlinearities (NEPv), where the nonlinearities are expressed by scalar functions that are defined by a quotient of linear functions of the eigenvector. The exact linearization relies on an equivalent multiparameter problem (MEP) that contains the exact solutions of the NEPv. Due to the characterization of MEPs in terms of a generalized eigenvalue problem this provides a direct way to compute all NEPv solutions for small problems, and it opens up the possibility to develop locally convergent iterative methods for larger problems. Moreover, the linear formulation allows us to easily determine the number of solutions of the NEPv. We propose two numerical schemes that exploit the structure of the linearization: inverse iteration and residual inverse iteration. We show how symmetry in the MEP can be used to improve reliability and reduce computational cost of both methods. Two numerical examples verify the theoretical results and a third example shows the potential of a hybrid scheme that is based on a combination of the two proposed methods., Comment: 23 pages, 7 figures

The discretisation of boundary integral equations for the scalar Helmholtz equation leads to large dense linear systems. Efficient boundary element methods (BEM), such as the fast multipole method (FMM) and $\Hmat$ based methods, focus on structured low-rank approximations of subblocks in these systems. It is known that the ranks of these subblocks increase linearly with the wavenumber. We explore a data-sparse representation of BEM-matrices valid for a range of frequencies, based on extracting the known phase of the Green's function. Algebraically, this leads to a Hadamard product of a frequency matrix with an $\Hmat$. We show that the frequency dependency of this $\Hmat$ can be determined using a small number of frequency samples, even for geometrically complex three-dimensional scattering obstacles. We describe an efficient construction of the representation by combining adaptive cross approximation with adaptive rational approximation in the continuous frequency dimension. We show that our data-sparse representation allows to efficiently sample the full BEM-matrix at any given frequency, and as such it may be useful as part of an efficient sweeping routine.

In this paper we solve $m$-parameter eigenvalue problems ($m$EPs), with $m$ any natural number by representing the problem using Tensor-Trains (TT) and designing a method based on this format. $m$EPs typically arise when separation of variables is applied to separable boundary value problems. Often, methods for solving $m$EP are restricted to $m = 3$, due to the fact that, to the best of our knowledge, no available solvers exist for $m>3$ and reasonable size of the involved matrices. In this paper, we prove that computing the eigenvalues of a $m$EP can be recast into computing the eigenvalues of TT-operators. We adapted the algorithm in \cite{Dolgov2014a} for symmetric eigenvalue problems in TT-format to an algorithm for solving generic $m$EPs. This leads to a subspace method whose subspace dimension does not depend on $m$, in contrast to other subspace methods for $m$EPS. This allows us to tackle $m$EPs with $m > 3$ and reasonable size of the matrices. We provide theoretical results and report numerical experiments. The MATLAB code is publicly available., Comment: 17 pages, 14 figures

Bayesian regression remains a simple but effective tool based on Bayesian inference techniques. For large-scale applications, with complicated posterior distributions, Markov Chain Monte Carlo methods are applied. To improve the well-known computational burden of Markov Chain Monte Carlo approach for Bayesian regression, we developed a multilevel Gibbs sampler for Bayesian regression of linear mixed models. The level hierarchy of data matrices is created by clustering the features and/or samples of data matrices. Additionally, the use of correlated samples is investigated for variance reduction to improve the convergence of the Markov Chain. Testing on a diverse set of data sets, speed-up is achieved for almost all of them without significant loss in predictive performance.

In this paper we extend the Residual Arnoldi method for calculating an extreme eigenvalue (e.g. largest real part, dominant,...) to the case where the matrices depend on parameters. The difference between this Arnoldi method and the classical Arnoldi algorithm is that in the former the residual is added to the subspace. We develop a Tensor-Krylov method that applies the Residual Arnoldi method (RA) for a grid of parameter points at the same time. The subspace contains an approximate Krylov space for all these points. Instead of adding the residuals for all parameter values to the subspace we create a low-rank approximation of the matrix consisting of these residuals and add only the column space to the subspace. In order to keep the computations efficient, it is needed to limit the dimension of the subspace and to restart once the subspace has reached the prescribed maximal dimension. The novelty of this approach is twofold. Firstly, we observed that a large error in the low-rank approximations is allowed without slowing down the convergence, which implies that we can do more iterations before restarting. Secondly, we pay particular attention to the way the subspace is restarted, since classical restarting techniques give a too large subspace in our case. We motivate why it is good enough to just keep the approximation of the searched eigenvector. At the end of the paper we extend this algorithm to shift-and-invert Residual Arnoldi method to calculate the eigenvalue close to a shift $\sigma$ for a specific parameter dependency. We provide theoretical results and report numerical experiments. The Matlab code is publicly available., Comment: 20 pages, 5 figures

In applications of linear algebra including nuclear physics and structural dynamics, there is a need to deal with uncertainty in the matrices. We focus on matrices that depend on a set of parameters $\omega$ and we are interested in the minimal eigenvalue of a matrix pencil $(A,B)$ with $A,B$ symmetric and $B$ positive definite. If $\omega$ can be interpreted as the realisation of random variables, one may be interested in statistical moments of the minimal eigenvalue. In order to obtain statistical moments, we need a fast evaluation of the eigenvalue as a function of $\omega$. Since this is costly for large matrices,we are looking for a small parametrized eigenvalue problem whose minimal eigenvalue makes a small error with the minimal eigenvalue of the large eigenvalue problem. The advantage, in comparison with a global polynomial approximation (on which, e.g., the polynomial chaos approximation relies), is that we do not suffer from the possible non-smoothness of the minimal eigenvalue. The small scale eigenvalue problem is obtained by projection of the large scale problem. Our main contribution is that for constructing the subspace we use multiple eigenvectors as well as derivatives of eigenvectors.We provide theoretical results and document numerical experiments regarding the beneficial effect of adding multiple eigenvectors and derivatives., Comment: 15 pages, 5 figures

The rational QZ method generalizes the QZ method by implicitly supporting rational subspace iteration. In this paper we extend the rational QZ method by introducing shifts and poles of higher multiplicity in the Hessenberg pencil, which is a pencil consisting of two Hessenberg matrices. The result is a multishift, multipole iteration on block Hessenberg pencils which allows one to stick to real arithmetic for a real input pencil. In combination with optimally packed shifts and aggressive early deflation as an advanced deflation technique we obtain an efficient method for the dense generalized eigenvalue problem. In the numerical experiments we compare the results with state-of-the-art routines for the generalized eigenvalue problem and show that we are competitive in terms of speed and accuracy.

Solving linear systems is often the computational bottleneck in real-life problems. Iterative solvers are the only option due to the complexity of direct algorithms or because the system matrix is not explicitly known. Here, we develop a two-level preconditioner for regularized least squares linear systems involving a feature or data matrix. Variants of this linear system may appear in machine learning applications, such as ridge regression, logistic regression, support vector machines and Bayesian regression. We use clustering algorithms to create a coarser level that preserves the principal components of the covariance or Gram matrix. This coarser level approximates the dominant eigenvectors and is used to build a subspace preconditioner accelerating the Conjugate Gradient method. We observed speed-ups for artificial and real-life data.

We propose subspace methods for 3-parameter eigenvalue problems. Such problems arise when separation of variables is applied to separable boundary value problems; a particular example is the Helmholtz equation in ellipsoidal and paraboloidal coordinates. While several subspace methods for 2-parameter eigenvalue problems exist, their extensions to three parameter setting seem to be challenging. An inherent difficulty is that, while for 2-parameter eigenvalue problems we can exploit a relation to Sylvester equations to obtain a fast Arnoldi type method, such a relation does not seem to exist when there are three or more parameters. Instead, we introduce a subspace iteration method with projections onto generalized Krylov subspaces that are constructed from scratch at every iteration using certain Ritz vectors as the initial vectors. Another possibility is a Jacobi--Davidson type method for three or more parameters, which we generalize from its 2-parameter counterpart. For both approaches, we introduce a selection criterion for deflation that is based on the angles between left and right eigenvectors. The Jacobi--Davidson approach is devised to locate eigenvalues close to a prescribed target, yet it often also performs well when eigenvalues are sought based on the proximity of one of the components to a prescribed target. The subspace iteration method is devised specifically for the latter task. The proposed approaches are suitable especially for problems where the computation of several eigenvalues is required with high accuracy. Matlab implementations of both methods have been made available in the package MultiParEig., Comment: 24 pages, 5 figures, 6 tables

We propose a rational QZ method for the solution of the dense, unsymmetric generalized eigenvalue problem. This generalization of the classical QZ method operates implicitly on a Hessenberg, Hessenberg pencil instead of on a Hessenberg, triangular pencil. Whereas the QZ method performs nested subspace iteration driven by a polynomial, the rational QZ method allows for nested subspace iteration driven by a rational function, this creates the additional freedom of selecting poles. In this article we study Hessenberg, Hessenberg pencils, link them to rational Krylov subspaces, propose a direct reduction method to such a pencil, and introduce the implicit rational QZ step. The link with rational Krylov subspaces allows us to prove essential uniqueness (implicit Q theorem) of the rational QZ iterates as well as convergence of the proposed method. In the proofs, we operate directly on the pencil instead of rephrasing it all in terms of a single matrix. Numerical experiments are included to illustrate competitiveness in terms of speed and accuracy with the classical approach. Two other types of experiments exemplify new possibilities. First we illustrate that good pole selection can be used to deflate the original problem during the reduction phase, and second we use the rational QZ method to implicitly filter a rational Krylov subspace in an iterative method.

We present a method for solving nonlinear eigenvalue problems using rational approximation. The method uses the AAA method by Nakatsukasa, S\`{e}te, and Trefethen to approximate the nonlinear eigenvalue problem by a rational eigenvalue problem and is embedded in the state space representation of a rational polynomial by Su and Bai. The advantage of the method, compared to related techniques such as NLEIGS and infinite Arnoldi, is the efficient computation by an automatic procedure. In addition, a set-valued approach is developed that allows building a low degree rational approximation of a nonlinear eigenvalue problem. The method perfectly fits the framework of the Compact rational Krylov methods (CORK and TS-CORK), allowing to efficiently solve large scale nonlinear eigenvalue problems. Numerical examples show that the presented framework is competitive with NLEIGS and usually produces smaller linearizations with the same accuracy but with less effort for the user.

High-dimensional data requires scalable algorithms. We propose and analyze three scalable and related algorithms for semi-supervised discriminant analysis (SDA). These methods are based on Krylov subspace methods which exploit the data sparsity and the shift-invariance of Krylov subspaces. In addition, the problem definition was improved by adding centralization to the semi-supervised setting. The proposed methods are evaluated on a industry-scale data set from a pharmaceutical company to predict compound activity on target proteins. The results show that SDA achieves good predictive performance and our methods only require a few seconds, significantly improving computation time on previous state of the art.

We revisit the numerical stability of the two-level orthogonal Arnoldi (TOAR) method for computing an orthonormal basis of a second--order Krylov subspace associated with two given matrices. We show that the computed basis is close (on certain subspace metric sense) to a basis for a second-order Krylov subspace associated with nearby coefficient matrices, provided that the norms of the given matrices are not too large or too small. Thus, the results in this work provide for the first time conditions that guarantee the numerical stability of the TOAR method in computing orthonormal bases of second-order Krylov subspaces. We also study scaling the quadratic problem for improving the numerical stability of the TOAR procedure when the norms of the matrices are too large or too small. We show that in many cases the TOAR procedure applied to scaled matrices is numerically stable when the scaling introduced by Fan, Lin and Van Dooren is used.

We consider the minimization or maximization of the $J$th largest eigenvalue of an analytic and Hermitian matrix-valued function, and build on Mengi et al. (2014, SIAM J. Matrix Anal. Appl., 35, 699-724). This work addresses the setting when the matrix-valued function involved is very large. We describe subspace procedures that convert the original problem into a small-scale one by means of orthogonal projections and restrictions to certain subspaces, and that gradually expand these subspaces based on the optimal solutions of small-scale problems. Global convergence and superlinear rate-of-convergence results with respect to the dimensions of the subspaces are presented in the infinite dimensional setting, where the matrix-valued function is replaced by a compact operator depending on parameters. In practice, it suffices to solve eigenvalue optimization problems involving matrices with sizes on the scale of tens, instead of the original problem involving matrices with sizes on the scale of thousands., Comment: 34 pages, 2 figures

The partial Schur factorization can be used to represent several eigenpairs of a matrix in a numerically robust way. Different adaptions of the Arnoldi method are often used to compute partial Schur factorizations. We propose here a technique to compute a partial Schur factorization of a nonlinear eigenvalue problem (NEP). The technique is inspired by the algorithm in [8], now called the infinite Arnoldi method. The infinite Arnoldi method is a method designed for NEPs, and can be interpreted as Arnoldi's method applied to a linear infinite-dimensional operator, whose reciprocal eigenvalues are the solutions to the NEP. As a first result we show that the invariant pairs of the operator are equivalent to invariant pairs of the NEP. We characterize the structure of the invariant pairs of the operator and show how one can carry out a modification of the infinite Arnoldi method by respecting the structure. This also allows us to naturally add the feature known as locking. We nest this algorithm with an outer iteration, where the infinite Arnoldi method for a particular type of structured functions is appropriately restarted. The restarting exploits the structure and is inspired by the well-known implicitly restarted Arnoldi method for standard eigenvalue problems. The final algorithm is applied to examples from a benchmark collection, showing that both processing time and memory consumption can be considerably reduced with the restarting technique.