Given a Hilbert space H and a finite measure space Ω, the approximation of a vector-valued function f:Ω→H by a k-dimensional subspace U⊂H plays an important role in dimension reduction techniques, such as reduced basis methods for solving parameter-dependent partial differential equations. For functions in the Lebesgue–Bochner space L2(Ω;H), the best possible subspace approximation error dk(2) is characterized by the singular values of f. However, for practical reasons, U is often restricted to be spanned by point samples of f. We show that this restriction only has a mild impact on the attainable error; there always exist k samples such that the resulting error is not larger than k+1⋅dk(2). Our work extends existing results by Binev et al. (2011) [3] on approximation in supremum norm and by Deshpande et al. (2006) [8] on column subset selection for matrices.

Abstract. By the addition of entropic regularization, multimarginal optimal transport problems can be transformed into tensor scaling problems, which can be solved numerically using the multimarginal Sinkhorn algorithm. The main computational bottleneck of this algorithm is the repeated evaluation of marginals. Recently, it has been suggested that this evaluation can be accelerated when the application features an underlying graphical model. In this work, we accelerate the computation further by combining the tensor network dual of the graphical model with additional low-rank approximations. We provide an example for the color transfer between several images, in which these additional low-rank approximations save more than [Formula: see text] of the computation time.

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.

The QR algorithm is the method of choice for computing all eigenvalues of a dense nonsymmetric matrix A . After an initial reduction to Hessenberg form, a QR iteration can be viewed as chasing a small bulge from the top left to the bottom right corner along the subdiagonal of A . To increase data locality and create potential for parallelism, modern variants of the QR algorithm perform several iterations simultaneously, which amounts to chasing a chain of several bulges instead of a single bulge. To make effective use of level 3 BLAS, it is important to pack these bulges as tightly as possible within the chain. In this work, we show that the tightness of the packing in existing approaches is not optimal and can be increased. This directly translates into a reduced chain length by 33% compared to the state-of-the-art LAPACK implementation of the QR algorithm. To demonstrate the impact of our idea, we have modified the LAPACK implementation to make use of the optimal packing. Numerical experiments reveal a uniform reduction of the execution time, without affecting stability or robustness.

The hierarchical Tucker format is a storage-efficient scheme to approximate and represent tensors of possibly high order. This article presents a Matlab toolbox, along with the underlying methodology and algorithms, which provides a convenient way to work with this format. The toolbox not only allows for the efficient storage and manipulation of tensors in hierarchical Tucker format but also offers a set of tools for the development of higher-level algorithms. Several examples for the use of the toolbox are given.

This paper proposes a novel approach to optimally solve volumetric registration problems. The proposed framework exploits parametric dictionaries for sparse volumetric representations, ℓ1dissimilarities and DC (Difference of Convex functions) decomposition. The SAD (sum of absolute differences) criterion is applied to the sparse representation of the reference volume and a DC decomposition of this criterion with respect to the transformation parameters is derived. This permits to employ a cutting plane algorithm for determining the optimal relative transformation parameters of the query volume. It further provides a guarantee for the global optimality of the obtained solution, which–to the best of our knowledge–is not offered by any other existing approach. A numerical validation demonstrates the effectiveness and the large potential of the proposed method.

Abstract We investigate the performance of the routines in LAPACK and the Successive Band Reduction (SBR) toolbox for the reduction of a dense matrix to tridiagonal form, a crucial preprocessing stage in the solution of the symmetric eigenvalue problem, on general‐purpose multi‐core processors. In response to the advances of hardware accelerators, we also modify the code in the SBR toolbox to accelerate the computation by off‐loading a significant part of the operations to a graphics processor (GPU). The performance results illustrate the parallelism and scalability of these algorithms on current high‐performance multi‐core and many‐core architectures. Copyright © 2010 John Wiley & Sons, Ltd.

This paper addresses the problem of image alignment based on random measurements. Image alignment consists of estimating the relative transformation between a query image and a reference image. We consider the specific problem where the query image is provided in compressed form in terms of linear measurements captured by a vision sensor. We cast the alignment problem as a manifold distance minimization problem in the linear subspace defined by the measurements. The transformation manifold that represents synthesis of shift, rotation, and isotropic scaling of the reference image can be given in closed form when the reference pattern is sparsely represented over a parametric dictionary. We show that the objective function can then be decomposed as the difference of two convex functions (DC) in the particular case where the dictionary is built on Gaussian functions. Thus, the optimization problem becomes a DC program, which in turn can be solved globally by a cutting plane method. The quality of the solution is typically affected by the number of random measurements and the condition number of the manifold that describes the transformations of the reference image. We show that the curvature, which is closely related to the condition number, remains bounded in our image alignment problem, which means that the relative transformation between two images can be determined optimally in a reduced subspace.

Abstract A parallel algorithm for reordering the eigenvalues in the real Schur form of a matrix is presented and discussed. Our novel approach adopts computational windows and delays multiple outside‐window updates until each window has been completely reordered locally. By using multiple concurrent windows the parallel algorithm has a high level of concurrency, and most work is level 3 BLAS operations. The presented algorithm is also extended to the generalized real Schur form. Experimental results for ScaLAPACK‐style Fortran 77 implementations on a Linux cluster confirm the efficiency and scalability of our algorithms in terms of more than 16 times of parallel speedup using 64 processors for large‐scale problems. Even on a single processor our implementation is demonstrated to perform significantly better compared with the state‐of‐the‐art serial implementation. Copyright © 2009 John Wiley & Sons, Ltd.

This article is concerned with the efficient numerical solution of the Lyapunov equation A T X + XA = - C with a stable matrix A and a symmetric positive semidefinite matrix C of possibly small rank. We discuss the efficient implementation of Hammarling's method and propose among other algorithmic improvements a block variant, which is demonstrated to perform significantly better than existing implementations. An extension to the discrete-time Lyapunov equation A T XA - X = - C is also described.

This article describes Fortran 77 subroutines for computing eigenvalues and invariant subspaces of Hamiltonian and skew-Hamiltonian matrices. The implemented algorithms are based on orthogonal symplectic decompositions, implying numerical backward stability as well as symmetry preservation for the computed eigenvalues. These algorithms are supplemented with balancing and block algorithms which can lead to considerable accuracy and performance improvements. As a by-product, an efficient implementation for computing symplectic QR decompositions is provided. We demonstrate the usefulness of the subroutines for several, practically relevant examples.

Block algorithms for reordering a selected set of eigenvalues in a standard or generalized Schur form are proposed. Efficiency is achieved by delaying orthogonal transformations and (optionally) making use of level 3 BLAS operations. Numerical experiments demonstrate that existing algorithms, as currently implemented in LAPACK, are outperformed by up to a factor of four.