Search

Abstract While interactive simulations have been mostly limited to Computer Graphics applications, new generations of Graphics Processing Units (GPUs) allow the realization of industrial-grade interactive 3D physics simulations. By combining an immersed boundary method with efficient GPU-based MINRES and CG solvers using a GPU-based geometric multigrid preconditioner, we demonstrate a fast industrial 3D computational mechanics solver. The various implementation aspects - specifically how they differ from similar concepts used in the Computer Graphics community - are discussed in detail. The proposed concept opens up new classes of industrial simulation applications allowing a democratization beyond today’s expert users, from designer centric simulation to operational and service decisions based on 3D simulations. To support this, we provide various benchmark cases including a real-world study of a simulation-based service decision for a damaged gear-box mount.

While interactive simulations have been mostly limited to Computer Graphics applications, new generations of Graphics Processing Units (GPUs) allow the realization of industrial-grade interactive 3D physics simulations. By combining an immersed boundary method with efficient GPU-based MINRES and CG solvers using a GPU-based geometric multigrid preconditioner, we demonstrate a fast industrial 3D computational mechanics solver. The various implementation aspects - specifically how they differ from similar concepts used in the Computer Graphics community - are discussed in detail. The proposed concept opens up new classes of industrial simulation applications allowing a democratization beyond today's expert users, from designer centric simulation to operational and service decisions based on 3D simulations. To support this, we provide various benchmark cases including a real-world study of a simulation-based service decision for a damaged gear-box mount. [ABSTRACT FROM AUTHOR]

In this study, a novel preconditioner based on the absolute-value block α -circulant matrix approximation is developed, specifically designed for nonsymmetric dense block lower triangular Toeplitz (BLTT) systems that emerge from the numerical discretization of evolutionary equations. Our preconditioner is constructed by taking an absolute-value of a block α -circulant matrix approximation to the BLTT matrix. To apply our preconditioner, the original BLTT linear system is converted into a symmetric form by applying a time-reversing permutation transformation. Then, with our preconditioner, the preconditioned minimal residual method (MINRES) solver is employed to solve the symmetrized linear system. With properly chosen α , the eigenvalues of the preconditioned matrix are proven to be clustered around ± 1 without any significant outliers. With the clustered spectrum, we show that the preconditioned MINRES solver for the preconditioned system has a convergence rate independent of system size. The efficacy of the proposed preconditioner is corroborated by our numerical experiments, which reveal that it attains optimal convergence. [ABSTRACT FROM AUTHOR]

In this paper, we generalize a fast Fourier transforms (FFTs) based preconditioner and propose a novel α -absolute value preconditioner for all-at-once systems from heat equations. Our preconditioner is symmetric positive definite and can also be computed efficiently using fast Fourier transforms or discrete sine transforms (DSTs). Furthermore, we prove that the corresponding preconditioned matrix has a unitary-plus-low-rank decomposition, and the eigenvalues of the preconditioned matrix are clustered at ±1, which leads to fast convergence rate of the preconditioned MINRES method. Finally, numerical examples on all-at-once systems from heat equations with different discretization scheme demonstrate the effectiveness of our new preconditioner. [ABSTRACT FROM AUTHOR]

We consider symmetric positive definite preconditioners for multiple saddle-point systems of block tridiagonal form, which can be applied within the Minres algorithm. We describe such a preconditioner for which the preconditioned matrix has only two distinct eigenvalues, |$1$| and |$-1$|⁠ , when the preconditioner is applied exactly. We discuss the relative merits of such an approach compared to a more widely studied block diagonal preconditioner, specify the computational work associated with applying the new preconditioner inexactly, and survey a number of theoretical results for the block diagonal case. Numerical results validate our theoretical findings. [ABSTRACT FROM AUTHOR]

In this work, we propose a simple yet generic preconditioned Krylov subspace method for a large class of nonsymmetric block Toeplitz all-at-once systems arising from discretizing evolutionary partial differential equations. Namely, our main result is to propose two novel symmetric positive definite preconditioners, which can be efficiently diagonalized by the discrete sine transform matrix. More specifically, our approach is to first permute the original linear system to obtain a symmetric one and subsequently develop desired preconditioners based on the spectral symbol of the modified matrix. Then, we show that the eigenvalues of the preconditioned matrix sequences are clustered around ± 1 , which entails rapid convergence when the minimal residual method is devised. Alternatively, when the conjugate gradient method on the normal equations is used, we show that our preconditioner is effective in the sense that the eigenvalues of the preconditioned matrix sequence are clustered around unity. An extension of our proposed preconditioned method is given for high-order backward difference time discretization schemes, which can be applied on a wide range of time-dependent equations. Numerical examples are given, also in the variable-coefficient setting, to demonstrate the effectiveness of our proposed preconditioners, which consistently outperforms an existing block circulant preconditioner discussed in the relevant literature. [ABSTRACT FROM AUTHOR]

A shortcoming of least-squares unrestricted factor analysis (UFA) procedures, which are widely used in psychometric applications is that a test statistic for assessing model-data fit cannot be easily derived from the minimum fit function value. This paper proposes a chi-square type goodness-of-fit test statistic intended for the principal-axis, MINRES, and minimum-rank UFA procedures. The statistic is empirically obtained via intensive simulation based on a two-stage approach. First, a distribution of minimum fit function values is obtained from a scenario in which the null hypothesis of perfect model-data fit holds. Second, the obtained statistic is non-linearly transformed so that it has its first four moments equal to those of the theoretical reference chi-square distribution with the appropriate degrees of freedom. Extensions of the basic statistic are next proposed that include comparative and relative indexes based on it. Tests of close-fit and power assessment derived from the basic statistic are also proposed.

In this work, we propose a novel preconditioned Krylov subspace method for solving an optimal control problem of wave equations, after explicitly identifying the asymptotic spectral distribution of the involved sequence of linear coefficient matrices from the optimal control problem. Namely, we first show that the all-at-once system stemming from the wave control problem is associated to a structured coefficient matrix-sequence possessing an eigenvalue distribution. Then, based on such a spectral distribution of which the symbol is explicitly identified, we develop an ideal preconditioner and two parallel-in-time preconditioners for the saddle point system composed of two block Toeplitz matrices. For the ideal preconditioner, we show that the eigenvalues of the preconditioned matrix-sequence all belong to the set (-3/2, -1/2) ∪ (1/2,3/2) well separated from zero, leading to mesh-independent convergence when the minimal residual method is employed. The proposed parallel-in-time preconditioners can be implemented efficiently using fast Fourier transforms or discrete sine transforms, and their effectiveness is theoretically shown in the sense that the eigenvalues of the preconditioned matrix-sequences are clustered around ±1, which leads to rapid convergence. When these parallel-in-time preconditioners are not fastly diagonalizable, we further propose modified versions which can be efficiently inverted. Several numerical examples are reported to verify our derived localization and spectral distribution result and to support the effectiveness of our proposed preconditioners and the related advantages with respect to the relevant literature. [ABSTRACT FROM AUTHOR]

A shortcoming of least-squares unrestricted factor analysis (UFA) procedures, which are widely used in psychometric applications is that a test statistic for assessing model-data fit cannot be easily derived from the minimum fit function value. This paper proposes a chi-square type goodness-of-fit test statistic intended for the principal-axis, MINRES, and minimum-rank UFA procedures. The statistic is empirically obtained via intensive simulation based on a two-stage approach. First, a distribution of minimum fit function values is obtained from a scenario in which the null hypothesis of perfect model-data fit holds. Second, the obtained statistic is non-linearly transformed so that it has its first four moments equal to those of the theoretical reference chisquare distribution with the appropriate degrees of freedom. Extensions of the basic statistic are next proposed that include comparative and relative indexes based on it. Tests of close-fit and power assessment derived from the basic statistic are also proposed. [ABSTRACT FROM AUTHOR]

We present a probabilistic analysis of two Krylov subspace methods for solving linear systems. We prove a central limit theorem for norms of the residual vectors that are produced by the conjugate gradient and MINRES algorithms when applied to a wide class of sample covariance matrices satisfying some standard moment conditions. The proof involves establishing a four‐moment theorem for the so‐called spectral measure, implying, in particular, universality for the matrix produced by the Lanczos iteration. The central limit theorem then implies an almost‐deterministic iteration count for the iterative methods in question. © 2022 Wiley Periodicals LLC. [ABSTRACT FROM AUTHOR]

When an iterative method is applied to solve the linear equation system in interior point methods (IPMs), the attention is usually placed on accelerating their convergence by designing appropriate preconditioners, but the linear solver is applied as a black box with a standard termination criterion which asks for a sufficient reduction of the residual in the linear system. Such an approach often leads to an unnecessary "oversolving" of linear equations. In this paper, an IPM that relies on an inner termination criterion not based on the residual of the linear system is introduced and analyzed. Moreover, new indicators for the early termination of the inner iterations are derived from a deep understanding of IPM needs. The new technique has been adapted to the conjugate gradient (CG) and to the minimum residual method (MINRES) applied in the IPM context. The new criterion has been tested on a set of quadratic optimization problems including compressed sensing, image processing, and instances with partial differential equation constraints, and it has been compared to standard residual tests with variable tolerance. Evidence gathered from these computational experiments shows that the new technique delivers significant improvements in terms of inner (linear) iterations and those translate into significant savings of the IPM solution time. [ABSTRACT FROM AUTHOR]

In this paper, we address the preconditioned iterative solution of the saddle-point linear systems arising from the (regularized) Interior Point method applied to linear and quadratic convex programming problems, typically of large scale. Starting from the well-studied Constraint Preconditioner, we review a number of inexact variants with the aim to reduce the computational cost of the preconditioner application within the Krylov subspace solver of choice. In all cases we illustrate a spectral analysis showing the conditions under which a good clustering of the eigenvalues of the preconditioned matrix can be obtained, which foreshadows (at least in case PCG/MINRES Krylov solvers are used), a fast convergence of the iterative method. Results on a set of large size optimization problems confirm that the Inexact variants of the Constraint Preconditioner can yield efficient solution methods. [ABSTRACT FROM AUTHOR]

The characterization of porous media via digital testing usually relies on intensive numerical computations that can be parallelized in GPUs. For absolute permeability estimation, Stokes flow simulations are carried out at the micro-structure to recover velocity fields that are used in upscaling with Darcy's law. Digital models of samples can be obtained via micro-computed tomography (μ CT) scans. As μ CT data is three-dimensional, meshes grow cubically with image dimensions, causing the numerical problem at hand to become compute- and memory-bound as either resolution improves or larger fields-of-view are considered. While the usual focus is on accelerating solvers, memory usage continues to be a significant limitation for analyses of representative volumes in relatively accessible hardware. In this work, we explore the possibility of implementing MINRES solvers in GPU that favor a reduction in memory allocation. These solvers are applied to matrix-free FEM-based permeability characterization of μ CT images. Our goal is to enable the study of 1000 3 voxel images in single GPU machines. Implementations that only require five, three, or two n -sized vectors of variables are presented, with n being the number of unknowns. Further, we employ a mesh numbering strategy that enables node-by-node massively parallel operations within a non-monolithic voxel-based pore space without storing connectivity tables. The proposed solvers, available through the open-source chfem software, are verified against analytical models for simple three-dimensional micro-structures, then are validated against numerical Digital Petrophysics benchmarks. A consumer-grade graphics card with 12GB of RAM is employed for the characterization of images with up to roughly 540 million voxels in a matter of tens of minutes. Stokes flow FEM-based simulations in meshes with 449 million degrees-of-freedom (DOFs) are carried out in 9 to 15 min, allocating less than 10GB in global memory. Finally, simulations on three 1000 3 carbon fiber domains, amounting to more than 3.7 billion DOFs, were run on a high-end GPU with 80GB of RAM in under 2.5 h, achieving very close agreement with flow-tube permeability experiments. • Open-source lightweight GPU solvers for FEM simulation of Stokes flow in porous media. • Developed implementations of MINRES that require allocation of 3 or 2 n-sized arrays. • Employed a voxel-based data structure to mesh only the pore space. • Performed absolute permeability analysis of giga-voxel images in desktop computers. • 3.7 billion DOFs simulations of highly porous fiber samples conducted with one GPU. [ABSTRACT FROM AUTHOR]

The iterative Krylov solver MINRES for linear equation systems has been implemented into auxiliary density perturbation theory. To this end, the MINRES solver was incorporated into the Eirola-Nevanlinna algorithm for large nonsymmetric matrices. As a result, the formal scaling of ADPT is reduced from O ( N aux 4 ) to O ( N aux 3 ), being N aux the number of auxiliary functions. Moreover, with MINRES this scaling can be further reduced by the use of the double asymptotic expansion of the two-center electron repulsion integrals. This state-of-the-art solver allows first-principles quantum-mechanical calculations of response properties for large systems with thousands of atoms at the nanometric scale. Comparison between the analytic and iterative solutions show excellent agreement for static and dynamical polarizabilities. To demonstrate the robustness of this newly implemented methodology, static polarizabilities of microbiologically relevant systems with more than 100,000 auxiliary functions and 28,000 basis functions are presented in this work. [ABSTRACT FROM AUTHOR]

The standard iterative refinement procedure for improving an approximate solution to the least squares problem minx ..., where ... n with m ≥ n has full rank, is based on solving the (m + n) X (m + n) augmented system with the aid of a QR factorization. In order to exploit multiprecision arithmetic, iterative refinement can be formulated to use three precisions, but the resulting algorithm converges only for a limited range of problems. We build an iterative refinement algorithm called GMRES-LSIR, analogous to the GMRES-IR algorithm developed for linear systems [E. Carson and N. J. Higham, SIAM J. Sci. Comput., 40 (2018), pp. A817--A847], that solves the augmented system using GMRES preconditioned by a matrix based on the computed QR factors. We explore two left preconditioners; the first has full off-diagonal blocks, and the second is block diagonal and can be applied in either left-sided or split form. We prove that for a wide range of problems the first preconditioner yields backward and forward errors for the augmented system of order the working precision under suitable assumptions on the precisions and the problem conditioning. Our proof does not extend to the block diagonal preconditioner, but our numerical experiments show that with this preconditioner the algorithm performs about as well in practice. The experiments also show that if we use MINRES in place of GMRES then the convergence is similar for sufficiently well conditioned problems but worse for the most ill conditioned ones. [ABSTRACT FROM AUTHOR]

Summary: Efficient and robust iterative methods are developed for solving the linear systems of equations arising from stochastic finite element methods for single phase fluid flow in porous media. Permeability is assumed to vary randomly in space according to some given correlation function. In the companion paper, herein referred to as Part 1, permeability was approximated using a truncated Karhunen‐Loève expansion (KLE). The stochastic variability of permeability is modeled using lognormal random fields and the truncated KLE is projected onto a polynomial chaos basis. This results in a stochastic nonlinear problem since the random fields are represented using polynomial chaos containing terms that are generally nonlinear in the random variables. Symmetric block Gauss‐Seidel used as a preconditioner for CG is shown to be efficient and robust for stochastic finite element method. [ABSTRACT FROM AUTHOR]

The non-diagonal elements of the observed covariances are more exactly reproduced by the factor loadings than by the model implied by the corresponding factor score predictors. This is a limitation to the validity of factor score predictors. It is therefore investigated whether it is possible to estimate factor loadings for which the model implied by the factor score predictors optimally reproduces the non-diagonal elements of the observed covariance matrix. Accordingly, loading estimates are proposed for which the model implied by the factor score predictors allows for a least-squares approximation of the non-diagonal elements of the observed covariance matrix. This estimation method is termed score predictor factor analysis and algebraically compared with Minres factor analysis as well as principal component analysis. A population-based and a sample-based simulation study was performed in order to compare score predictor factor analysis, Minres factor analysis, and principal component analysis. It turns out that the non-diagonal elements of the observed covariance matrix can more exactly be reproduced from the factor score predictors computed from score predictor factor analysis than from the factor score predictors computed from Minres factor analysis and from principal components.

The non-diagonal elements of the observed covariances are more exactly reproduced by the factor loadings than by the model implied by the corresponding factor score predictors. This is a limitation to the validity of factor score predictors. It is therefore investigated whether it is possible to estimate factor loadings for which the model implied by the factor score predictors optimally reproduces the non-diagonal elements of the observed covariance matrix. Accordingly, loading estimates are proposed for which the model implied by the factor score predictors allows for a least-squares approximation of the non-diagonal elements of the observed covariance matrix. This estimation method is termed score predictor factor analysis and algebraically compared with Minres factor analysis as well as principal component analysis. A population-based and a sample-based simulation study was performed in order to compare score predictor factor analysis, Minres factor analysis, and principal component analysis. It turns out that the non-diagonal elements of the observed covariance matrix can more exactly be reproduced from the factor score predictors computed from score predictor factor analysis than from the factor score predictors computed from Minres factor analysis and from principal components. [ABSTRACT FROM AUTHOR]

We develop a robust solver for a mixed finite element convex splitting scheme for the Cahn-Hilliard equation. The key ingredient of the solver is a preconditioned minimal residual algorithm (with a multigrid preconditioner) whose performance is independent of the spacial mesh size and the time step size for a given interfacial width parameter. The dependence on the interfacial width parameter is also mild. [ABSTRACT FROM AUTHOR]

In this paper, we develop adaptive inexact versions of iterative algorithms applied to finite element discretizations of the linear Stokes problem. We base our developments on an equilibrated stress a posteriori error estimate distinguishing the different error components, namely the discretization error component, the (inner) algebraic solver error component, and possibly the outer algebraic solver error component for algorithms of the Uzawa type. We prove that our estimate gives a guaranteed upper bound on the total error, as well as a polynomial-degree-robust local efficiency, and this on each step of the employed iterative algorithm. Our adaptive algorithms stop the iterations when the corresponding error components do not have a significant influence on the total error. The developed framework covers all standard conforming and conforming stabilized finite element methods on simplicial and rectangular parallelepipeds meshes in two or three space dimensions and an arbitrary algebraic solver. Implementation into the FreeFem++ programming language is invoked and numerical examples showcase the performance of our a posteriori estimates and of the proposed adaptive strategies. As example, we choose here the unpreconditioned and preconditioned Uzawa algorithm and the preconditioned minimum residual algorithm, in combination with the Taylor-Hood discretization. [ABSTRACT FROM AUTHOR]

Saddle-point systems, i.e., structured linear systems with symmetric matrices are considered. A modified implementation of (preconditioned) MINRES is derived which allows subvectors of the residual to be monitored individually. Compared to the implementation from the textbook of [H. C. Elman, D. J. Silvester, and A. J. Wathen, Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics, 2nd ed., Oxford University Press, Oxford, 2014], our method requires one extra vector of storage and no additional applications of the preconditioner. Numerical experiments are included. [ABSTRACT FROM AUTHOR]

This paper addresses the question of what exactly is an analogue of the preconditioned steepest descent (PSD) algorithm in the case of a symmetric indefinite system with an SPD preconditioner. We show that a basic PSD-like scheme for an SPD-preconditioned symmetric indefinite system is mathematically equivalent to the restarted PMINRES, where restarts occur after every two steps. A convergence bound is derived. If certain information on the spectrum of the preconditioned system is available, we present a simpler PSD-like algorithm that performs only one-dimensional residual minimization. Our primary goal is to bridge the theoretical gap between optimal (PMINRES) and PSD-like methods for solving symmetric indefinite systems, as well as point out situations where the PSD-like schemes can be used in practice. [ABSTRACT FROM AUTHOR]

We derive an efficient solution method for ill-posed PDE-constrained optimization problems with total variation regularization. This regularization technique allows discontinuous solutions, which is desirable in many applications. Our approach is to adapt the split Bregman technique to handle such PDE-constrained optimization problems. This leads to an iterative scheme where we must solve a linear saddle point problem in each iteration. We prove that the spectra of the corresponding saddle point operators are almost contained in three bounded intervals, not containing zero, with a very limited number of isolated eigenvalues. Krylov subspace methods handle such operators very well and thus provide an efficient algorithm. In fact, we can guarantee that the number of iterations needed cannot grow faster than $$O([\ln (\alpha ^{-1})]^2)$$ as $$\alpha \rightarrow 0$$ , where $$\alpha $$ is a small regularization parameter. Moreover, in our numerical experiments we demonstrate that one can expect iteration numbers of order $$O(\ln (\alpha ^{-1}))$$ . [ABSTRACT FROM AUTHOR]

Circulant preconditioning for symmetric Toeplitz linear systems is well established; theoretical guarantees of fast convergence for the conjugate gradient method are descriptive of the convergence seen in computations. This has led to robust and highly efficient solvers based on use of the fast Fourier transform exactly as originally envisaged in [G. Strang, Stud. Appl. Math., 74 (1986), pp. 171-176]. For nonsymmetric systems, the lack of generally descriptive convergence theory for most iterative methods of Krylov type has provided a barrier to such a comprehensive guarantee, though several methods have been proposed and some analysis of performance with the normal equations is available. In this paper, by the simple device of reordering, we rigorously establish a circulant preconditioned short recurrence Krylov subspace iterative method of minimum residual type for nonsymmetric (and possibly highly nonnormal) Toeplitz systems. Convergence estimates similar to those in the symmetric case are established. [ABSTRACT FROM AUTHOR]

SUMMARY This paper is concerned with the development of efficient iterative methods for solving the linear system of equations arising from stochastic FEMs for single-phase fluid flow in porous media. It is assumed that the conductivity coefficient varies randomly in space according to some given correlation function and is approximated using a truncated Karhunen-Loève expansion. Distinct discretizations of the deterministic and stochastic spaces are required for implementations of the stochastic FEM. In this paper, the deterministic space is discretized using classical finite elements and the stochastic space using a polynomial chaos expansion. The highly structured linear systems which result from this discretization mean that Krylov subspace iterative solvers are extremely effective. The performance of a range of preconditioned iterative methods is investigated and evaluated in terms of robustness with respect to mesh size and variability of the conductivity coefficient. An efficient symmetric block Gauss-Seidel preconditioner is proposed for problems in which the conductivity coefficient has a large standard deviation.The companion paper, herein, referred to as Part 2, considers the situation in which Gaussian random fields are transformed into lognormal ones by projecting the truncated Karhunen-Loève expansion onto a polynomial chaos basis. This results in a stochastic nonlinear problem because the random fields are represented using polynomial chaos containing terms that are generally nonlinear in the random variables. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In nonlinear geostatistical inverse problems, it often takes a significant amount of computational cost to form linear geostatistical inversion systems by linearizing the forward model. More specifically, the storage cost associated with the sensitivity matrix H ( m × n, where m and n are the numbers of measurements and unknowns, respectively) is high, especially when both m and n are large in for instance, 3-D tomography problems. In this research, instead of explicitly forming and directly solving the linear geostatistical inversion system, we use MINRES, a Krylov subspace method, to solve it iteratively. During each iteration in MINRES, we only compute the products Hx and H T x for any appropriately sized vectors x, for which we solve the forward problem twice. As a result, we reduce the memory requirement from [ABSTRACT FROM AUTHOR]

We consider deflation and augmentation techniques for accelerating the convergence of Krylov subspace methods for the solution of nonsingular linear algebraic systems. Despite some formal similarity, the two techniques are conceptually different from preconditioning. Deflation (in the sense the term is used here) "removes" certain parts from the operator making it singular, while augmentation adds a subspace to the Krylov subspace (often the one that is generated by the singular operator); in contrast, preconditioning changes the spectrum of the operator without making it singular. Deflation and augmentation have been used in a variety of methods and settings. Typically, deflation is combined with augmentation to compensate for the singularity of the operator, but both techniques can be applied separately. We introduce a framework of Krylov subspace methods that satisfy a Galerkin condition. It includes the families of orthogonal residual and minimal residual methods. We show that in this framework augmentation can be achieved either explicitly or, equiva-lently, implicitly by projecting the residuals appropriately and correcting the approximate solutions in a final step. We study conditions for a breakdown of the deflated methods, and we show several possibilities to avoid such breakdowns for the deflated minimum residual (MINRES) method. Numerical experiments illustrate properties of different variants of deflated MINRES analyzed in this paper. [ABSTRACT FROM AUTHOR]

The progressive GMRES algorithm, introduced by Beckermann and Reichel in 2008, is a residual-minimizing short-recurrence Krylov subspace method for solving a linear system in which the coefficient matrix has a low-rank skew-Hermitian part. We analyze this algorithm, observing a critical instability that makes the method unsuitable for some problems. To work around this issue we introduce a different short-term recurrence method based on Krylov subspaces for such matrices, which can be used as either a solver or a preconditioner. Numerical experiments compare this method to alternative algorithms. [ABSTRACT FROM AUTHOR]

For the classical saddle-point problem, we present precisely two intervals containing the positive and the negative eigenvalues of the preconditioned matrix, respectively, when the inexact version of the symmetric positive definite preconditioner introduced in Section 2.1 of Gill et al. [Preconditioners for indefinite systems arising in optimization, SIAM J. Matrix Anal. Appl. 13 (1992), pp. 292–311] is employed. The model of Stokes problem is used to test the effectiveness of the presented bounds as well as the quality of the symmetric positive definite preconditioner. [ABSTRACT FROM AUTHOR]

An iterative method LSMR is presented for solving linear systems Ax = baud least-squares problems min ||Ax - b||2, with A being sparse or a fast linear operator. LSMR is based on the Golub-Kahan bidiagonalizatiou process. It is analytically equivalent to the MINRES method applied to the normal equation AT Ax = ATb, so that the quantities ||AT rk|| are monotonically decreasing (where rk = b - Axk is the residual for the current iterate xk). We observe in practice that ||rk|| also decreases monotonically, so that compared to LSQR (for which only ||rk is monotonic) it is safer to terminate LSMR early. We also report some experiments with reorthogonalization. [ABSTRACT FROM AUTHOR]

CG, SYMMLQ, and MINRES are Krylov subspace methods for solving symmetric systems of linear equations. When these methods are applied to an incompatible system (that is, a singular symmetric least-squares problem), CG could break down and SYMMLQ's solution could explode, while MINRES would give a learnt-squares solution but not necessarily the minimum-length (pseudoinverse) solution. This understanding motivates us to design a MINRES-like algorithm to compute minimum-length solutions to singular symmetric systems. MINRES uses QR factors of the tridiagonal matrix from the Lanczos process (where R is upper-tridiagonal). MINRES-QLP uses a QLP decomposition (where rotations on the right reduce R to lower-tridiagonal form). On ill-conditioned systems (singular or not), MINRES-QLP can give more accurate solutions than MINRES. We derive preconditioned MINRES-QLP, new stopping rules, and better estimates of the solution and residual norms, the matrix norm, and the condition number. [ABSTRACT FROM AUTHOR]

We present a detailed convergence analysis of preconditioned MINRES for approximately solving the linear systems that arise when Rayleigh quotient iteration is used to compute the lowest eigenpair of a symmetric positive definite matrix. We provide insight into the initial stagnation of MINRES iteration in both a qualitative and quantitative way and show that the convergence of MINRES mainly depends on how quickly the unique negative eigenvalue of the preconditioned shifted coefficient matrix is approximated by its corresponding harmonic Ritz value. By exploring when the negative Ritz value appears in MINRES iteration, we obtain a better understanding of the limitation of preconditioned MINRES in this context and the virtue of a new type of preconditioner with "tuning." A comparison of MINRES with SYMMLQ in this context is also given. Finally, we show that tuning based on a rank-2 modification can be applied with little additional cost to guarantee positive definiteness of the tuned preconditioner. [ABSTRACT FROM AUTHOR]

When diagonal values are missing or excluded, MINRES is a natural continuous model for the core/periphery structure of a symmetric social network matrix. Symmetric models, however, are not so useful when dealing with asymmetric data. Singular value decomposition (SVD) is a natural choice to model asymmetry, but this method also requires the presence of diagonal values. In this paper we offer an alternative, more general, approach to continuous core/periphery structures, the minimum residual singular value decomposition (MINRES/SVD), where each node in the network receives two indices, an “in-coreness” and an “out-coreness.” The algorithm for computing these coreness vectors is a least squares computation similar to, but distinct from the SVD, again because of the missing diagonal values. And in contrast to the standard, symmetric MINRES algorithm, we can more accurately model asymmetric matrices. This allows us to distinguish, for example, countries in the world economy that are more in the exporting core than they are in the importing core. We propose two nested PRE (proportional reduction of error) measures of fit: (1) the PRE from the MINRES vector with respect to the data and (2) the PRE of the product of the two MINRES/SVD vectors. Applying the resulting method to citations between journals and to international trade in clothing, we illustrate insights gained from being able to model asymmetrical flow patterns. Finally, two permutation tests are introduced to test independently for the MINRES and MINRES/SVD results. [Copyright &y& Elsevier]

Abstract: Mixed electrostatic and magnetostatic finite element formulations are considered. Solution methods for the resulting indefinite algebraic systems are investigated. Methods developed for the mixed formulations of the Stokes equations are modified in order to apply to the Maxwell equations: an efficient block preconditioner is proposed and a stabilised formulation is described. The different methods are applied to 2D and 3D examples. [Copyright &y& Elsevier]

Abstract: For an Vandermonde matrix with translated Chebyshev zero nodes, it is discovered that admits an explicit QR decomposition with the R-factor consisting of the coefficients of the translated Chebyshev polynomials. This decomposition then leads to an exact expression for the Frobenius condition number of its submatrix (so-called a rectangular Vandermonde matrix), bounds on individual singular value, and more. It is explained how these results can be used to establish asymptotically optimal lower bounds on condition numbers of real rectangular Vandermonde matrices and nearly optimally conditioned real rectangular Vandermonde matrices on a given interval. Extensions are also made for with nodes being zeros of any translated orthogonal polynomials other than Chebyshev ones. Similar results hold for with translated Chebyshev extreme nodes, too, owing to that admits an explicit QR-like decomposition. Close formulas of or tight bounds on the residuals are also presented for the conjugate gradient method, the minimal residual method, and the generalized minimal residual method on certain linear systems with A having eigenvalues the same as the nodes mentioned above. As a by-product, they yield positive definite linear systems for which the residuals by the conjugate gradient method are always comparable to the existing error bounds for all iteration steps. [Copyright &y& Elsevier]

When GMRES (or a similar minimum-residual algorithm such as RRGMRES, MINRES, or MR-II) is applied to a discrete ill-posed problem with a square matrix, in some cases the iterates can be considered as regularized solutions. We show how to precondition these methods in such a way that the iterations take into account a smoothing norm for the solution. This technique is well established for CGLS, but it does not immediately carry over to minimum-residual methods when the smoothing norm is a seminorm or a Sobolev norm. We develop a new technique which works for any smoothing norm of the form ∥Lx∥2 and which preserves symmetry if the coefficient matrix is symmetric. We also discuss the efficient implementation of our preconditioning technique, and we demonstrate its performance with numerical examples in one and two dimensions. [ABSTRACT FROM AUTHOR]

We discuss the efficient solution of a long sequence of slowly varying linear systems arising in computations for diffuse optical tomographic imaging. The reconstruction of three-dimensional absorption and scattering information by matching computed solutions from a parameterized model to measured data leads to a nonlinear least squares problem that we solve using the Gauss-Newton method with a line search. This algorithm requires the solution of a long sequence of linear systems. Each choice of parameters in the nonlinear least squares algorithm results in a different matrix describing the optical properties of the medium. These matrices change slowly from one step to the next, but may change significantly over many steps. For each matrix we must solve a set of linear systems with multiple shifts and multiple right-hand sides. For this problem, we derive strategies for recycling Krylov subspace information that exploit properties of the application and the nonlinear optimization algorithm to significantly reduce the total number of iterations over all linear systems. Furthermore, we introduce variants of GCRO that exploit symmetry and that allow simultaneous solution of multiple shifted systems using a single Krylov subspace in combination with recycling. Although we focus on a particular application and optimization algorithm, our approach is applicable generally to problems where sequences of linear systems must be solved. This may guide other researchers to exploit the opportunities of tunable solvers. We provide results for two sets of numerical experiments to demonstrate the effectiveness of the resulting method. [ABSTRACT FROM AUTHOR]

A necessary and sufficient condition for the consecutive powers of an interval matrix to converge to the null matrix was established by Mayer. Motivated by the issue of globally asymptotic stability of Takagi­Sugeno free fuzzy systems with time-varying uncertainty, we study the conditions for the infinite products of a finite number of interval matrices to converge to the null matrix. As an application, convergence to null matrix of infinite products of the associated finite interval matrices implies the globally asymptotic stability of Takagi­Sugeno free fuzzy systems with time-varying uncertainty. [ABSTRACT FROM AUTHOR]

We consider the weighted least-squares (WLS) problem with a very ill-conditioned weight matrix. WLS problems arise in many applications including linear programming, electrical networks, boundary value problems, and structures. Because of roundoff errors, standard iterative methods for solving a WLS problem with ill-conditioned weights may not give the correct answer. Indeed, the difference between the true and computed solution (forward error) may be large. We propose an iterative algorithm, called MINRES-L, for solving WLS problems. The MINRES-L method is the application of MINRES, a Krylov-space method due to Paige and Saunders [SIAM J. Numer. Anal., 12 (1975), pp. 617–629], to a certain layered linear system. Using a simplified model of the effects of roundoff error, we prove that MINRES-L ultimately yields answers with small forward error. We present computational experiments for some applications. [ABSTRACT FROM AUTHOR]

The three-term Lanczos process for a symmetric matrix leads to bases for Krylov subspaces of increasing dimension. The Lanczos basis, together with the recurrence coefficients, can be used for the solution of symmetric indefinite linear systems, by solving a reduced system in one way or another. This leads to well-known methods: MINRES (minimal residual), GMRES (generalized minimal residual), and SYMMLQ (symmetric LQ). We will discuss in what way and to what extent these approaches differ in their sensitivity to rounding errors. In our analysis we will assume that the Lanczos basis is generated in exactly the same way for the different methods, and we will not consider the errors in the Lanczos process itself. We will show that the method of solution may lead, under certain circumstances, to large additional errors, which are not corrected by continuing the iteration process. Our findings are supported and illustrated by numerical examples. [ABSTRACT FROM AUTHOR]

Expressions and bounds are derived for the residual norm in GMRES. It is shown that the minimal residual norm is large as long as the Krylov basis is well-conditioned. For scaled Jordan blocks the minimal residual norm is expressed in terms of eigenvalues and departure from normality. For normal matrices the minimal residual norm is expressed in terms of products of relative eigenvalue differences. [ABSTRACT FROM AUTHOR]

In this paper we present three theorems which give insight into the regularizing properties of MINRES. While our theory does not completely characterize the regularizing behavior of the algorithm, it provides a partial explanation of the observed behavior of the method. Unlike traditional attempts to explain the regularizing properties of Krylov subspace methods, our approach focuses on convergence properties of the residual rather than on convergence analysis of the harmonic Ritz values. The import of our analysis is illustrated by two examples. In particular, our theoretical and numerical results support the following important observation: in some circumstances the dimension of the optimal Krylov subspace can be much smaller than the number of the components of the truncated spectral solution that must be computed to attain comparable accuracy. [ABSTRACT FROM AUTHOR]

A new algorithm to obtain the least-squares or MINRES solution in common factor analysis is presented. It is based on the up-and-down Marquardt algorithm developed by the present authors for a general nonlinear least-squares problem. Experiments with some numerical models and some empirical data sets showed that the algorithm worked nicely and that SMC (Squared Multiple Correlation) performed best among four sets of initial values for common variances but that the solution might sometimes be very sensitive to fluctuations in the sample covariance matrix. [ABSTRACT FROM AUTHOR]