Search

A reduced-dimension robust Capon beamforming method using Krylov subspace techniques (RDRCB) is a diagonal loading algorithm with low complexity, fast convergence and strong anti-interference ability. The diagonal loading level of RDRCB is known to become invalid if the initial value of the Newton iteration method is incorrect and the Hessel matrix is non-positive definite. To improve the robustness of RDRCB, an improved RDRCB (IRDRCB) was proposed in this study. We analyzed the variation in the loading factor with the eigenvalues of the reduced-dimensional covariance matrix and derived the upper and lower boundaries of the diagonal loading level; the diagonal loading level of the IRDRCB was kept within the bounds mentioned above. The computer simulation results show that the IRDRCB can effectively solve the problems of a sharp decline in the signal-to-noise ratio gain and an invalid diagonal loading level. The experimental results demonstrate that the interference noise of the IRDRCB is 3~5 dB higher than that of conventional adaptive beamforming, and the computational complexity is reduced by 15% to 20% compared with that of the RCB method. [ABSTRACT FROM AUTHOR]

Abstract In the design process of large adaptive mirrors numerical simulations represent the first step to evaluate the system design compliance in terms of performance, stability and robustness. For the next generation of Extremely Large Telescopes increased system dimensions and bandwidths lead to the need of modeling not only the deformable mirror alone, but also all the system supporting structure or even the full telescope. The capability to perform the simulations with an acceptable amount of time and computational resources is highly dependent on finding appropriate methods to reduce the size of the resulting dynamic models. In this paper we present a framework developed together with the company Microgate to create a reduced order structural model of a large adaptive mirror as a preprocessing step to the control system simulations. The reduced dynamic model is then combined with the remaining system components allowing to simulate the full adaptive mirror in a computationally efficient way. We analyze the feasibility of our reduced models for Microgate’s prototype of the adaptive mirror of the Giant Magellan Telescope.

In the design process of large adaptive mirrors numerical simulations represent the first step to evaluate the system design compliance in terms of performance, stability and robustness. For the next generation of Extremely Large Telescopes increased system dimensions and bandwidths lead to the need of modeling not only the deformable mirror alone, but also all the system supporting structure or even the full telescope. The capability to perform the simulations with an acceptable amount of time and computational resources is highly dependent on finding appropriate methods to reduce the size of the resulting dynamic models. In this paper we present a framework developed together with the company Microgate to create a reduced order structural model of a large adaptive mirror as a preprocessing step to the control system simulations. The reduced dynamic model is then combined with the remaining system components allowing to simulate the full adaptive mirror in a computationally efficient way. We analyze the feasibility of our reduced models for Microgate's prototype of the adaptive mirror of the Giant Magellan Telescope. [ABSTRACT FROM AUTHOR]

Summary: In this paper, we describe and analyze the spectral properties of several exact block preconditioners for a class of double saddle point problems. Among all these, we consider an inexact version of a block triangular preconditioner providing extremely fast convergence of the (F)GMRES method. We develop a spectral analysis of the preconditioned matrix showing that the complex eigenvalues lie in a circle of center (1,0)$$ \left(1,0\right) $$ and radius 1, while the real eigenvalues are described in terms of the roots of a third order polynomial with real coefficients. Numerical examples are reported to illustrate the efficiency of inexact versions of the proposed preconditioners, and to verify the theoretical bounds. [ABSTRACT FROM AUTHOR]

Krylov subspace methods for solving linear systems of equations involving skew-symmetric matrices have gained recent attention. Numerical equivalences among Krylov subspace methods for nonsingular skew-symmetric linear systems have been given in Greif et al. [SIAM J. Matrix Anal. Appl., 37 (2016), pp. 1071–1087]. In this work, we extend the results of Greif et al. to singular skew-symmetric linear systems. In addition, we systematically study three Krylov subspace methods (called S 3 CG, S 3 MR, and S 3 LQ) for solving shifted skew-symmetric linear systems. They all are based on Lanczos triangularization for skew-symmetric matrices and correspond to CG, MINRES, and SYMMLQ for solving symmetric linear systems, respectively. To the best of our knowledge, this is the first work that studies S 3 LQ. We give some new theoretical results on S 3 CG, S 3 MR, and S 3 LQ. We also provide relations among the three methods and those based on Golub–Kahan bidiagonalization and Saunders–Simon–Yip tridiagonalization. Numerical examples are given to illustrate our theoretical findings. [ABSTRACT FROM AUTHOR]

When applied to linear vector sequences, extrapolation methods are equivalent to Krylov subspace methods. Both types of methods can be expressed as particular cases of the multisecant equations, the secant method generalized to higher dimensions. Through these equations, there is also equivalence with a variety of quasi-Newton methods. This paper presents a framework to connect these various methods. [ABSTRACT FROM AUTHOR]

When the conjugate gradient (CG) method for solving linear algebraic systems was formulated about 70 years ago by Lanczos, Hestenes, and Stiefel, it was considered an iterative process possessing a mathematical finite termination property. With the deep insight of the original authors, CG was placed into a very rich mathematical context, including links with Gauss quadrature and continued fractions. The optimality property of CG was described via a normalized weighted polynomial least squares approximation to zero. This highly nonlinear problem explains the adaptation of CG iterates to the given data. Karush and Hayes immediately considered CG in infinite dimensional Hilbert spaces and investigated its superlinear convergence. Since then, the view of CG, as well as other Krylov subspace methods developed in the meantime, has changed. Today these methods are considered primarily as computational tools, and their behavior is typically characterized using linear upper bounds, or heuristics based on clustering of eigenvalues. Such simplifications limit the mathematical understanding of Krylov subspace methods, and also negatively affect their practical application. This paper offers a different perspective. Focusing on CG and the generalized minimal residual (GMRES) method, it presents mathematically important as well as practically relevant phenomena that uncover their behavior through a discussion of computed examples. These examples provide an easily accessible approach that enables understanding of the methods, while pointers to more detailed analyses in the literature are given. This approach allows readers to choose the level of depth and thoroughness appropriate for their intentions. Some of the points made in this paper illustrate well known facts. Others challenge mainstream views and explain existing misunderstandings. Several points refer to recent results leading to open problems. We consider CG and GMRES crucially important for the mathematical understanding, further development, and practical applications also of other Krylov subspace methods. The paper additionally addresses the motivation of preconditioning. [ABSTRACT FROM AUTHOR]

With the recent emergence of mixed precision hardware, there has been a renewed interest in its use for solving numerical linear algebra problems fast and accurately. The solution of total least squares problems, i.e., solving min E , r ‖ [ E , r ] ‖ F subject to (A + E) x = b + r , arises in numerous applications. Solving this problem requires finding the smallest singular value and corresponding right singular vector of [ A , b ] , which is challenging when A is large and sparse. An efficient algorithm for this case due to Björck et al. (SIAM J. Matrix Anal. Appl. 22(2), 413–429 2000), called RQI-PCGTLS, is based on Rayleigh quotient iteration coupled with the preconditioned conjugate gradient method. We develop a mixed precision variant of this algorithm, RQI-PCGTLS-MP, in which up to three different precisions can be used. We assume that the lowest precision is used in the computation of the preconditioner and give theoretical constraints on how this precision must be chosen to ensure stability. In contrast to standard least squares, for total least squares, the resulting constraint depends not only on the matrix A , but also on the right-hand side b . We perform a number of numerical experiments on model total least squares problems used in the literature, which demonstrate that our algorithm can attain the same accuracy as RQI-PCGTLS albeit with a potential convergence delay due to the use of low precision. Performance modeling shows that the mixed precision approach can achieve up to a 4 × speedup depending on the size of the matrix and the number of Rayleigh quotient iterations performed. [ABSTRACT FROM AUTHOR]

This paper is mainly focused on the solution of Sylvester matrix differential equations with time-independent coefficients. We propose a new approach based on the construction of a particular constant solution which allows to construct an approximate solution of the differential equation from that of the corresponding algebraic equation. Moreover, when the matrix coefficients of the differential equation are large, we combine the constant solution approach with Krylov subspace methods for obtaining an approximate solution of the Sylvester algebraic equation, and thus form an approximate solution of the large-scale Sylvester matrix differential equation. We establish some theoretical results including error estimates and convergence as well as relations between the residuals of the differential and its corresponding algebraic Sylvester matrix equation. We also give explicit benchmark formulas for the solution of the differential equation. To illustrate the efficiency of the proposed approach, we perform numerous numerical tests and make various comparisons with other methods for solving Sylvester matrix differential equations. [ABSTRACT FROM AUTHOR]

In this paper, we present a comprehensive framework for studying Krylov subspace methods used to solve the linear system A x = f . These methods aim to achieve convergence within a specified number of iterations, denoted by m, given a particular initial estimate vector x 0 and its corresponding residual r 0 = f - A x 0 . Our analysis focuses on the minimal polynomial Φ m of degree m of A for the vector r 0 . We establish that these methods encompass Petrov-Galerkin methods and minimal seminorm methods as special cases. Additionally, we demonstrate that minimal seminorm methods satisfy implicit Petrov-Galerkin conditions. We provide a general formulation for the iterates based on generalized inverses. The choice of a specific left inverse and the method of constructing the Krylov basis are crucial distinguishing factors among different Krylov subspace methods. We describe and analyze the mathematical properties of these methods, emphasizing their dependency on two matrices. Notably, we prove that CMRH and QMR, as specific instances, also satisfy implicit Petrov-Galerkin orthogonality conditions. Furthermore, we explore techniques to improve the convergence behavior of these methods by carefully selecting vectors in their implementations. Through our investigation, we aim to deepen the understanding of Krylov subspace methods, provide insights into their convergence properties, and identify potential enhancements. We also consider some Krylov subspace methods, which are of product-type methods. In this case, the kth residual r k associated with the approximation x k of the exact solution is given by r k = Ψ k (A) Φ k (A) r 0 , and Ψ k is a polynomial of fixed or variable degree. We will examine particular choices of Ψ k involving local convergence, smoothing, fixed memory, and cost for each iteration. We will also give an enhancement of some product-type methods such as CGS. To illustrate the performance of the derived algorithms, we provide some numerical examples. [ABSTRACT FROM AUTHOR]

The PageRank model, which was first proposed by Google for its web search engine application, has since become a popular computational tool in a wide range of scientific fields, including chemistry, bioinformatics, neuroscience, bibliometrics, social networks, and others. PageRank calculations necessitate the use of fast computational techniques with low algorithmic and memory complexity. In recent years, much attention has been paid to Krylov subspace algorithms for solving difficult PageRank linear systems, such as those with large damping parameters close to one. In this article, we examine the full orthogonalization method (FOM). We present a convergence study of the method that extends and clarifies part of the conclusions reached in Zhang et al. (J Comput Appl Math. 2016; 296:397–409.). Furthermore, we demonstrate that FOM is breakdown free when solving singular PageRank linear systems with index one and we investigate the effect of using weighted inner‐products instead of conventional inner‐products in the orthonormalization procedure on FOM convergence. Finally, we develop a shifted polynomial preconditioner that takes advantage of the special structure of the PageRank linear system and has a good ability to cluster most of the eigenvalues, making it a good choice for an iterative method like FOM or GMRES. Numerical experiments are presented to support the theoretical findings and to evaluate the performance of the new weighted preconditioned FOM PageRank solver in comparison to other established solvers for this class of problem, including conventional stationary methods, hybrid combinations of stationary and Krylov subspace methods, and multi‐step splitting strategies. [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]

Computer implementations of vector orthogonalization algorithms produce a sequence of supposedly orthogonal vectors, but rounding-errors can cause loss of orthogonality and rank. Nevertheless these computational algorithms can be very effective as parts of various methods. We develop a general theory based on the augmented orthogonal matrix developed in that can be applied to any such algorithm. This can be combined with a rounding-error analysis of the algorithm to analyze its finite-precision behavior. We apply this combination to prove that a particular Lanczos tridiagonalization of a Hermitian matrix always computes components for which backward-stable solutions to Ax=b, A=AH, exist. If an appropriate rounding-error analysis is available, the approach can apparently be applied to any computation producing a sequence of supposedly orthogonal n-vectors, where a linear combination of these vectors is intended to approximate some quantity. [ABSTRACT FROM AUTHOR]

Image deblurring (ID) plays a vital role in various applications, including photography, medical imaging, and surveillance. Traditional ID methods often face challenges in preserving fine details and handling complex blurring scenarios due to expensive calculations. In this paper, a novel approach utilizing conformable fractional derivative (CFD) to address these challenges and improve the effectiveness of ID is presented. CFD offer a flexible framework for capturing and exploiting the non-local and non-linear properties inherent in images. Additionally, we propose a new circulant preconditioned matrix that ensures a fast convergence rate. The proven analytical property of the new preconditioner ensures fast convergence rates. The efficiency and efficacy of our algorithm is demonstrated by numerical experiments.

A reduced-dimension robust Capon beamforming method using Krylov subspace techniques (RDRCB) is a diagonal loading algorithm with low complexity, fast convergence and strong anti-interference ability. The diagonal loading level of RDRCB is known to become invalid if the initial value of the Newton iteration method is incorrect and the Hessel matrix is non-positive definite. To improve the robustness of RDRCB, an improved RDRCB (IRDRCB) was proposed in this study. We analyzed the variation in the loading factor with the eigenvalues of the reduced-dimensional covariance matrix and derived the upper and lower boundaries of the diagonal loading level; the diagonal loading level of the IRDRCB was kept within the bounds mentioned above. The computer simulation results show that the IRDRCB can effectively solve the problems of a sharp decline in the signal-to-noise ratio gain and an invalid diagonal loading level. The experimental results demonstrate that the interference noise of the IRDRCB is 3~5 dB higher than that of conventional adaptive beamforming, and the computational complexity is reduced by 15% to 20% compared with that of the RCB method.

This paper tackles efficient methods for Bayesian inverse problems with priors based on Whittle–Matérn Gaussian random fields. The Whittle–Matérn prior is characterized by a mean function and a covariance operator that is taken as a negative power of an elliptic differential operator. This approach is flexible in that it can incorporate a wide range of prior information including nonstationary effects, but it is currently computationally advantageous only for integer values of the exponent. In this paper, we derive an efficient method for handling all admissible noninteger values of the exponent. The method first discretizes the covariance operator using finite elements and quadrature, and uses preconditioned Krylov subspace solvers for shifted linear systems to efficiently apply the resulting covariance matrix to a vector. This approach can be used for generating samples from the distribution in two different ways: by solving a stochastic partial differential equation, and by using a truncated Karhunen–Loève expansion. We show how to incorporate this prior representation into the infinite-dimensional Bayesian formulation, and show how to efficiently compute the maximum a posteriori estimate, and approximate the posterior variance. Although the focus of this paper is on Bayesian inverse problems, the techniques developed here are applicable to solving systems with fractional Laplacians and Gaussian random fields. Numerical experiments demonstrate the performance and scalability of the solvers and their applicability to model and real-data inverse problems in tomography and a time-dependent heat equation. [ABSTRACT FROM AUTHOR]

We consider the iterative solution of large linear systems of equations in which the coefficient matrix is the sum of two terms, a sparse matrix A and a possibly dense, rank deficient matrix of the form γUUT, where γ > 0 is a parameter which in some applications may be taken to be 1. The matrix A itself can be singular, but we assume that the symmetric part of A is positive semidefinite and that A+γUUT is nonsingular. Linear systems of this form arise frequently in fields like optimization, fluid mechanics, computational statistics, and others. We investigate preconditioning strategies based on an alternating splitting approach combined with the use of the Sherman-Morrison-Woodbury matrix identity. The potential of the proposed approach is demonstrated by means of numerical experiments on linear systems from different application areas. [ABSTRACT FROM AUTHOR]

We propose algorithms for efficient time integration of large systems of oscillatory second order ordinary differential equations (ODEs) whose solutions can be expressed in terms of trigonometric matrix functions. Our algorithms are based on a residual notion for second order ODEs, which allows us to extend the “residual-time restarting” Krylov subspace framework—which was recently introduced for exponential and φ -functions occurring in time integration of first order ODEs—to our setting. We then show that the computational cost can be further reduced in many cases by using our restarting in the Gautschi cosine scheme. We analyze residual convergence in terms of Faber and Chebyshev series and supplement these theoretical results by numerical experiments illustrating the efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

The solution of the Poisson equation raised from large-scale problems requires iterative techniques. Multilevel and Krylov subspace methods have been proven to be the most efficient among various iterative methods. Recently, the scheduled relaxation Jacobi technique has been developed, which can be used as a stand-alone iterative solver as well as a preconditioner to the Krylov subspace methods. The relaxed Jacobi (RJ) method has also been implemented as a smoother in the multigrid method, with no-post smoothening. Here, the focus is to test the performance of relaxed Jacobi when applied to the large scale Poisson problems. Multigrid methods with both post-smoothening and pre-smoothening operations have been conducted in this paper. The methodology is applied to a rectangular domain using structured Cartesian grids. Also, multigrid methods with relaxed Jacobi smoothers are used as preconditioners to Krylov subspace solvers, and their performances are compared with the red-black Gauss-Seidel smoothers. Similar to the results in the literature, RJ smoothers to multigrid techniques provide better results than Gauss-Seidel smoothers when no-post smoothening operations are carried out. However, the use of post-smoothening operations changed the entire dynamic of the RJ smoothers. [ABSTRACT FROM AUTHOR]

In this paper, we consider the numerical solution of a large complex linear system with a saddle-point form obtained by the discretization of the time-harmonic eddy-current optimal control problem. A new Schur complement is proposed for this algebraic system, extending it to both the block-triangular preconditioner and the structured preconditioner. A theoretical analysis proves that the eigenvalues of block-triangular and structured preconditioned matrices are located in the interval [1/2, 1]. Numerical simulations show that two new preconditioners coupled with a Krylov subspace acceleration have good feasibility and effectiveness and are superior to some existing efficient algorithms. [ABSTRACT FROM AUTHOR]

Three explicit time integration schemes are compared for solving nonlinear heat conduction problems, local iteration monotone scheme, nonlinear exponential Euler scheme and a scheme based on the hyperbolic model of heat conduction, where an artificial second order time derivative term is added to stabilize the computations. The local iteration monotone and exponential Euler schemes are monotone and allow for a sufficiently large time step size. The local iteration monotone scheme is based on a special Chebyshev polynomial approximation, whereas the exponential Euler scheme employs a restarted Krylov subspace procedure. For these two schemes we propose an adaptive time step selection strategy which leads to a significant reduction in computational costs. [ABSTRACT FROM AUTHOR]

The PageRank model is widely utilized for analyzing a variety of scientific issues beyond its original application in modeling web search engines. In recent years, considerable research effort has focused on developing high-performance iterative methods to solve this model, particularly when the dimension is exceedingly large. However, due to the ever-increasing extent and size of data networks in various applications, the computational requirements of the PageRank model continue to grow. This has led to the development of new techniques that aim to reduce the computational complexity required for the solution. In this paper, we present a recursive 5-type lumping algorithm combined with a two-stage elimination strategy that leverage characteristics about the nonzero structure of the underlying network and the nonzero values of the PageRank coefficient matrix. This method reduces the initial PageRank problem to the solution of a remarkably smaller and sparser linear system. As a result, it leads to significant cost reductions for computing PageRank solutions, particularly in scenarios involving large and/or multiple damping factors. Numerical experiments conducted on over 50 real-world networks demonstrate that the proposed methods can effectively exploit characteristics of PageRank problems for efficient computations.

Iterative methods and especially Krylov subspace methods (KSM) are a very useful numerical tool in solving for large and sparse linear systems problems arising in science and engineering modeling. More recently, the nested loop KSM have been proposed that improve the convergence of the traditional KSM. In this article, we review the residual cutting (RC) and the generalized residual cutting (GRC) that are nested loop methods for large and sparse linear systems problems. We also show that GRC is a KSM that is equivalent to Orthomin with a variable preconditioning. We use the modified Gram–Schmidt method to derive a stable GRC algorithm. We show that GRC presents a general framework for constructing a class of "hybrid" (nested) KSM based on inner loop method selection. We conduct numerical experiments using nonsymmetric indefinite matrices from a widely used library of sparse matrices that validate the efficiency and the robustness of the proposed methods. [ABSTRACT FROM AUTHOR]

Forsythe formulated a conjecture about the asymptotic behavior of the restarted conjugate gradient method in 1968. We translate several of his results into modern terms, and pose an analogous version of the conjecture (originally formulated only for symmetric positive definite matrices) for symmetric and nonsymmetric matrices. Our version of the conjecture uses a two-sided or cross iteration with the given matrix and its transpose, which is based on the projection process used in the Arnoldi (or for symmetric matrices the Lanczos) algorithm. We prove several new results about the limiting behavior of this iteration, but the conjecture still remains largely open. We hope that our paper motivates further research that eventually leads to a proof of the conjecture. [ABSTRACT FROM AUTHOR]

Total fractional-order variation (TFOV) in image deblurring problems can reduce/remove the staircase problems observed with the image deblurring technique by using the standard total variation (TV) model. However, the discretization of the Euler–Lagrange equations associated with the TFOV model generates a saddle point system of equations where the coefficient matrix of this system is dense and ill conditioned (it has a huge condition number). The ill-conditioned property leads to slowing of the convergence of any iterative method, such as Krylov subspace methods. One treatment for the slowness property is to apply the preconditioning technique. In this paper, we propose a block triangular preconditioner because we know that using the exact triangular preconditioner leads to a preconditioned matrix with exactly two distinct eigenvalues. This means that we need at most two iterations to converge to the exact solution. However, we cannot use the exact preconditioner because the Shur complement of our system is of the form S = K * K + λ L α which is a huge and dense matrix. The first matrix, K * K , comes from the blurred operator, while the second one is from the TFOV regularization model. To overcome this difficulty, we propose two preconditioners based on the circulant and standard TV matrices. In our algorithm, we use the flexible preconditioned GMRES method for the outer iterations, the preconditioned conjugate gradient (PCG) method for the inner iterations, and the fixed point iteration (FPI) method to handle the nonlinearity. Fast convergence was found in the numerical results by using the proposed preconditioners. [ABSTRACT FROM AUTHOR]

Two different block preconditioners are introduced and studied for solving a class of double saddle point linear systems. We provide an eigenvalue analysis for the preconditioned matrices, with special focus on their inexact variants, and give some numerical experiments to illustrate the performance of the studied preconditioning techniques. [ABSTRACT FROM AUTHOR]

With the recent realization of exascale performance by Oak Ridge National Laboratory's Frontier supercomputer, reducing communication in kernels like QR factorization has become even more imperative. Low-synchronization Gram-Schmidt methods, first introduced in Świrydowicz et al. (Numer. Lin. Alg. Appl. 28(2):e2343, 2020), have been shown to improve the scalability of the Arnoldi method in high-performance distributed computing. Block versions of low-synchronization Gram-Schmidt show further potential for speeding up algorithms, as column-batching allows for maximizing cache usage with matrix-matrix operations. In this work, low-synchronization block Gram-Schmidt variants from Carson et al. (Linear Algebra Appl. 638:150–195, 2022) are transformed into block Arnoldi variants for use in block full orthogonalization methods (BFOM) and block generalized minimal residual methods (BGMRES). An adaptive restarting heuristic is developed to handle instabilities that arise with the increasing condition number of the Krylov basis. The performance, accuracy, and stability of these methods are assessed via a flexible benchmarking tool written in MATLAB. The modularity of the tool additionally permits generalized block inner products, like the global inner product. [ABSTRACT FROM AUTHOR]

In this paper, we propose an approach based on Krylov subspace methods for the solution of ℓ 1 regularized logistic regression problem. The main idea is to transform the constrained ℓ 2 - ℓ 1 minimization problem obtained by applying the IRLS method to a ℓ 2 - ℓ 2 one that allow regularization matrices in the usual 2-norm regularization term. The regularization parameter that controls the equilibrium between the minimization of the two terms of the ℓ 2 - ℓ 2 minimization problem can be then chosen inexpensively by solving some reduced minimization problems related to generalized cross-validation (GCV) methods. These reduced problems can be obtained after a few iterations of Krylov subspace based methods. The goal of our simulation study is directed toward the variable selection and the prediction accuracy performance of the proposed method in solving a ℓ 1 regularized logistic regression problem in large dimensional data with different correlation structures among predictors. Finally, real data are used to confirm the efficiency of the proposed method in terms of the computational cost. [ABSTRACT FROM AUTHOR]

A coarse grid correction (CGC) approach is proposed to enhance the efficiency of the matrix exponential and φ matrix function evaluations. The approach is intended for iterative methods computing the matrix-vector products with these functions. It is based on splitting the vector by which the matrix function is multiplied into a smooth part and a remaining part. The smooth part is then handled on a coarser grid, whereas the computations on the original grid are carried out with a relaxed stopping criterion tolerance. Estimates on the error are derived for the two-grid and multigrid variants of the proposed CGC algorithm. Numerical experiments demonstrate the efficiency of the algorithm when it is employed in combination with Krylov subspace and Chebyshev polynomial expansion methods. [ABSTRACT FROM AUTHOR]

A common way to approximate F(A)b--the action of a matrix function on a vector--is to use the Arnoldi approximation. Since a new vector needs to be generated and stored in every iteration, one is often forced to rely on restart algorithms which are either not efficient, not stable, or applicable only to restricted classes of functions. We present a new representation of the error of the Arnoldi iterates if the function F is given as a Laplace transform. Based on this representation we build an efficient and stable restart algorithm. In doing so we extend earlier work for the class of Stieltjes functions which are special Laplace transforms. We report several numerical experiments including comparisons with the restart method for Stieltjes functions. [ABSTRACT FROM AUTHOR]

In this article a preconditioned version of the Delayed Weighted Gradient Method (DWGM) is presented and analyzed. In addition to the convergence, some nice properties as the A- orthogonality of the current transformed gradient with all the previous gradient vectors as well as finite convergence are demonstrated. Numerical experimentation is also offered, exposing the benefits of preconditioning.

In this paper, we consider the numerical solution of a large complex linear system with a saddle-point form obtained by the discretization of the time-harmonic eddy-current optimal control problem. A new Schur complement is proposed for this algebraic system, extending it to both the block-triangular preconditioner and the structured preconditioner. A theoretical analysis proves that the eigenvalues of block-triangular and structured preconditioned matrices are located in the interval [1/2, 1]. Numerical simulations show that two new preconditioners coupled with a Krylov subspace acceleration have good feasibility and effectiveness and are superior to some existing efficient algorithms.

Image deblurring models with a mean curvature functional has been widely used to preserve edges and remove the staircase effect in the resulting images. However, the Euler-Lagrange equations of a mean curvature model can be used to solve fourth-order non-linear integro-differential equations. Furthermore, the discretization of fourth-order non-linear integro-differential equations produces an ill-conditioned system so that the numerical schemes like Krylov subspace methods (conjugate gradient etc.) have slow convergence. In this paper, we propose an augmented Lagrangian method for a mean curvature-based primal form of the image deblurring problem. A new circulant preconditioned matrix is introduced to overcome the problem of slow convergence when employing a conjugate gradient method inside of the augmented Lagrangian method. By using the proposed new preconditioner fast convergence has been observed in the numerical results. Moreover, a comparison with the existing numerical methods further reveal the effectiveness of the preconditioned augmented Lagrangian method.

The block Cimmino is a parallel hybrid row-block projection iterative method successfully used for solving general sparse linear systems. However, the convergence of the method degrades when angles between subspaces spanned by the row-blocks are far from being orthogonal. The density of columns as well as the numerical values of their nonzeros are more likely to contribute to the nonorthogonality between row-blocks. We propose a novel scheme to handle such "dense" columns. The proposed scheme forms a reduced system by separating these columns and the respective rows from the original coefficient matrix and handling them via the Schur complement. Then the angles between subspaces spanned by the row-blocks of the reduced system are expected to be closer to orthogonal, and the reduced system is solved efficiently by the block conjugate gradient (CG) accelerated block Cimmino in fewer iterations. We also propose a novel metric for selecting "dense" columns considering the numerical values. The proposed metric establishes an upper bound on the sum of inner products between row-blocks. Then we propose an efficient algorithm for computing the proposed metric for the columns. Extensive numerical experiments for a wide range of linear systems confirm the effectiveness of the proposed scheme by achieving fewer iterations and faster parallel solution time compared to the classical CG accelerated block Cimmino algorithm. [ABSTRACT FROM AUTHOR]

Source extension is a reformulation of inverse problems in wave propagation, that at least in some cases leads to computationally tractable iterative solution methods. The core subproblem in all source extension methods is the solution of a linear inverse problem for a source (right hand side in a system of wave equations) through minimization of data error in the least squares sense with soft imposition of physical constraints on the source via an additive quadratic penalty. For an acoustic formulation for sources supported on a surface, with a soft contraint enforcing concentration at a point, a variant of the time reversal method from photoacoustic tomography provides an approximate solution. This approximate inverse can be used to precondition Krylov space iteration for rapid convergence to the solution of the core subproblem in this setting. Numerical examples illustrate the effectiveness of this preconditioner. [ABSTRACT FROM AUTHOR]

The block version of GMRES (BGMRES) is most advantageous over the single right hand side (RHS) counterpart when the cost of communication is high while the cost of floating point operations is not. This is the particular case on modern graphics processing units (GPUs), while it is generally not the case on traditional central processing units (CPUs). In this paper, experiments on both GPUs and CPUs are shown that compare the performance of BGMRES against GMRES as the number of RHS increases, with a particular forcus on GPU performance. The experiments indicate that there are many cases in which BGMRES is slower than GMRES on CPUs, but faster on GPUs. Furthermore, when varying the number of RHS on the GPU, there is an optimal number of RHS where BGMRES is clearly most advantageous over GMRES. A computational model for the GPU is developed using hardware specific parameters, providing insight towards how the qualitative behavior of BGMRES changes as the number of RHS increase, and this model also helps explain the phenomena observed in the experiments. [ABSTRACT FROM AUTHOR]

Error contaminated linear approximation problems appear in a large variety of applications. The presence of redundant or irrelevant data complicates their solution. It was shown that such data can be removed by the core reduction yielding a minimally dimensioned subproblem called the core problem. Direct (SVD or Tucker decomposion-based) reduction has been introduced previously for problems with matrix models and vector, or matrix, or tensor observations; and also for problems with bilinear models. For the cases of vector and matrix observations a Krylov subspace method, the generalized Golub-Kahan bidiagonalization, can be used to extract the core problem. In this paper, we first unify previously studied variants of linear approximation problems under the general framework of a multilinear approximation problem. We show how the direct core reduction can be extended to it. Then we show that the generalized Golub-Kahan bidiagonalization yields the core problem for any multilinear approximation problem. This further allows one to prove various properties of core problems, in particular, we give upper bounds on the multiplicity of singular values of reduced matrices. [ABSTRACT FROM AUTHOR]

In this paper a variant of nonlinear exponential Euler scheme is proposed for solving nonlinear heat conduction problems. The method is based on nonlinear iterations where at each iteration a linear initial-value problem has to be solved. We compare this method to the backward Euler method combined with nonlinear iterations. For both methods we show monotonicity and boundedness of the solutions and give sufficient conditions for convergence of the nonlinear iterations. Numerical tests are presented to examine performance of the two schemes. The presented exponential Euler scheme is implemented based on restarted Krylov subspace methods and, hence, is essentially explicit (involves only matrix-vector products). [ABSTRACT FROM AUTHOR]

In this paper, we propose a generalized shift-HSS (denoted by SFHSS) iteration method for solving nonsingular saddle point systems with nonsymmetric positive definite (1, 1)-block sub-matrix, and theoretically verify its convergence property. In addition, we discuss the algebraic properties of the resulted SFHSS preconditioner and estimate the sharp eigenvalue bounds of the related preconditioned matrix. Finally, numerical experiments are given to support our theoretical results and reveal that the new method is feasible and effective.

In this paper we present general-purpose preconditioners for regularized augmented systems, and their corresponding normal equations, arising from optimization problems. We discuss positive definite preconditioners, suitable for CG and MINRES. We consider "sparsifications" which avoid situations in which eigenvalues of the preconditioned matrix may become complex. Special attention is given to systems arising from the application of regularized interior point methods to linear or nonlinear convex programming problems. [ABSTRACT FROM AUTHOR]

We propose a novel preconditioned inexact primal-dual interior point method for constrained convex quadratic programming problems. The algorithm we describe invokes the preconditioned conjugate gradient method on a new reduced Schur complement Karush-Kuhn-Tucker (KKT) system in implicit form. In contrast to standard approaches, the Schur complement formulation we consider enables reuse of the factorization of the KKT matrix with rows and columns corresponding to inequality constraints excluded across all interior point iterations. Further, two new preconditioners are presented for the resulting reduced system that alleviate the ill-conditioning associated with slack variables in primal-dual interior point methods. Each of the preconditioners we propose also provably reduces the number of unique eigenvalues for the coefficient matrix and thus the conjugate gradient method iteration count. One preconditioner is efficient when the number of equality constraints is small, while the other is efficient when the number of remaining degrees of freedom is small. Numerical experiments with synthetic problems and problems from the Maros-Mészáros quadratic programming collection show that our preconditioned inexact interior point solvers are effective at improving conditioning and reducing cost. Across all test problems for which the direct method is not fastest, our preconditioned methods achieve a reduction in cost by a geometric mean of 1.432 relative to the best alternative preconditioned method for each problem. [ABSTRACT FROM AUTHOR]

Image deblurring models with a mean curvature functional has been widely used to preserve edges and remove the staircase effect in the resulting images. However, the Euler-Lagrange equations of a mean curvature model can be used to solve fourth-order non-linear integro-differential equations. Furthermore, the discretization of fourth-order non-linear integro-differential equations produces an ill-conditioned system so that the numerical schemes like Krylov subspace methods (conjugate gradient etc.) have slow convergence. In this paper, we propose an augmented Lagrangian method for a mean curvature-based primal form of the image deblurring problem. A new circulant preconditioned matrix is introduced to overcome the problem of slow convergence when employing a conjugate gradient method inside of the augmented Lagrangian method. By using the proposed new preconditioner fast convergence has been observed in the numerical results. Moreover, a comparison with the existing numerical methods further reveal the effectiveness of the preconditioned augmented Lagrangian method. [ABSTRACT FROM AUTHOR]

Analyzing massive spatial datasets using a Gaussian process model poses computational challenges. This is a problem prevailing heavily in applications such as environmental modeling, ecology, forestry and environmental health. We present a novel approximate inference methodology that uses profile likelihood and Krylov subspace methods to estimate the spatial covariance parameters and makes spatial predictions with uncertainty quantification for point-referenced spatial data. “Kryging” combines Kriging and Krylov subspace methods and applies for both observations on regular grid and irregularly spaced observations, and for any Gaussian process with a stationary isotropic (and certain geometrically anisotropic) covariance function, including the popular Matérn covariance family. We make use of the block Toeplitz structure with Toeplitz blocks of the covariance matrix and use fast Fourier transform methods to bypass the computational and memory bottlenecks of approximating log-determinant and matrix-vector products. We perform extensive simulation studies to show the effectiveness of our model by varying sample sizes, spatial parameter values and sampling designs. A real data application is also performed on a dataset consisting of land surface temperature readings taken by the MODIS satellite. Compared to existing methods, the proposed method performs satisfactorily with much less computation time and better scalability. [ABSTRACT FROM AUTHOR]