Search

SUMMARY This special issue contains a selection of papers from the Sixth International Workshop on the Numerical Solution of Markov Chains, held in Williamsburg, Virginia on September 16-17, 2010. The papers cover a broad range of topics including perturbation theory for absorbing chains, bounding techniques, steady-state and transient solution methods, multilevel algorithms, preconditioning, and applications. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The goal of the present paper is the design of embeddings of a general sparse graph into a set of points in ℝd for appropriate d ≥ 2. The embeddings that we are looking at aim to keep vertices that are grouped in communities together and keep the rest apart. To achieve this property, we utilize coarsening that respects possible community structures of the given graph. We employ a hierarchical multilevel coarsening approach that identifies communities (strongly connected groups of vertices) at every level. The multilevel strategy allows any given (presumably expensive) graph embedding algorithm to be made into a more scalable (and faster) algorithm. We demonstrate the presented approach on a number of given embedding algorithms and large‐scale graphs and achieve speed‐up over the methods in a recent paper. [ABSTRACT FROM AUTHOR]

In this paper, enlightened by the effectiveness of Anderson acceleration (AA), a well‐established technique for accelerating fixed‐point solvers, we first present the Anderson accelerating modulus‐based matrix splitting (AAMS) algorithms for a class of horizontal nonlinear complementarity problems. Then, by introducing the strong semi‐smoothness of the absolute value function, we establish the local convergence theory of the AAMS algorithms. More importantly, we provide the optimal parameter for the AAMS algorithms, which is independent of iteration and applicable to other reduced MS algorithms. Finally, the numerical experiments are conducted to clarify the efficiency and practicability of the AAMS algorithms and its optimal parameter, and the effects of two parameters (both derived from AA) of the AAMS algorithms are analyzed. [ABSTRACT FROM AUTHOR]

Summary: This paper studies a low‐communication algorithm for solving elliptic PDEs on high‐performance machines, the nested iteration with range decomposition (NIRD) algorithm. Previous work has shown that NIRD converges to a high level of accuracy within a small, fixed number of iterations (usually one or two) when applied to simple elliptic problems. This paper makes some improvements to the NIRD algorithm (including the addition of adaptivity during preprocessing, wider choice of partitioning functions, and modified error measurement) that enhance the method's accuracy and scalability, especially on more difficult problems. In addition, an updated convergence proof is presented based on heuristic assumptions that are supported by numerical evidence. Furthermore, a new performance model is developed that shows increased performance benefits for NIRD when problems are more expensive to solve using traditional methods. Finally, extensive testing on a variety of elliptic problems provides additional insight into the behavior of NIRD and additional evidence that NIRD achieves excellent convergence on a wide class of elliptic PDEs and, as such, should be a very competitive method for solving PDEs on large parallel computers. [ABSTRACT FROM AUTHOR]

Summary: In this paper, we propose a fast algorithm for computing the spectral radii of symmetric nonnegative tensors. In particular, by this proposed algorithm, we are able to obtain the spectral radii of weakly reducible symmetric nonnegative tensors without requiring the partition of the tensors. As we know, it is very costly to determine the partition for large‐sized weakly reducible tensors. Numerical results are reported to show that the proposed algorithm is efficient and also able to compute the spectral radii of large‐sized tensors. As an application, we present an algorithm for testing the positive definiteness of Z‐tensors. By this algorithm, it is guaranteed to determine the positive definiteness for any Z‐tensor. [ABSTRACT FROM AUTHOR]

In this paper, we apply the Anderson acceleration technique to the existing relaxation fixed‐point iteration for solving the multilinear PageRank. In order to reduce computational cost, we further consider the periodical version of the Anderson acceleration. The convergence of the proposed algorithms is discussed. Numerical experiments on synthetic and real‐world datasets are performed to demonstrate the advantages of the proposed algorithms over the relaxation fixed‐point iteration and the extrapolated shifted fixed‐point method. In particular, we give a strategy for choosing the quasi‐optimal parameters of the associated algorithms when they are applied to solve the test problems with different sizes but the same structure. [ABSTRACT FROM AUTHOR]

Summary: The tensor SVD (t‐SVD) for third‐order tensors, previously proposed in the literature, has been applied successfully in many fields, such as computed tomography, facial recognition, and video completion. In this paper, we propose a method that extends a well‐known randomized matrix method to the t‐SVD. This method can produce a factorization with similar properties to the t‐SVD, but it is more computationally efficient on very large data sets. We present details of the algorithms and theoretical results and provide numerical results that show the promise of our approach for compressing and analyzing image‐based data sets. We also present an improved analysis of the randomized and simultaneous iteration for matrices, which may be of independent interest to the scientific community. We also use these new results to address the convergence properties of the new and randomized tensor method as well. [ABSTRACT FROM AUTHOR]

Summary: This paper presents some recent advances for parallel‐in‐time methods applied to linear elasticity. With recent computer architecture changes leading to stagnant clock speeds, but ever increasing numbers of cores, future speedups will be available through increased concurrency. Thus, sequential algorithms, such as time stepping, will suffer a bottleneck. This paper explores multigrid reduction in time (MGRIT) for an important application area, linear elasticity. Previously, efforts at parallel‐in‐time for elasticity have experienced difficulties, for example, the beating phenomenon. As a result, practical parallel‐in‐time algorithms for this application area currently do not exist. This paper proposes some solutions made possible by MGRIT (e.g., slow temporal coarsening and FCF‐relaxation) and, more importantly, a different formulation of the problem that is more amenable to parallel‐in‐time methods. Using a recently developed convergence theory for MGRIT and Parareal, we show that the changed formulation of the problem avoids the instability issues and allows the reduction of the error using two temporal grids. We then extend our approach to the multilevel case, where we demonstrate how slow temporal coarsening improves convergence. The paper ends with supporting numerical results showing a practical algorithm enjoying speedup benefits over the sequential algorithm. [ABSTRACT FROM AUTHOR]

Domain decomposition methods for finite element problems using a partition based on the underlying finite element mesh have been extensively studied, in this paper, we discuss algebraic extensions of the class of overlapping domain decomposition algorithms for general sparse matrices. The subproblems are created with an overlapping partition of the graph corresponding to the sparsity structure of the matrix. These algebraic domain decomposition methods are especially useful for unstructured mesh problems. We also discuss some difficulties encountered in the algebraic extension, particularly the issues related to the coarse solver. [ABSTRACT FROM AUTHOR]

In the present paper, we describe an adaptive modified rational global Lanczos algorithm for model-order reduction problems using multipoint moment matching-based methods. The major problem of these methods is the selection of some interpolation points. We first propose a modified rational global Lanczos process and then we derive Lanczos-like equations for the global case. Next, we propose adaptive techniques for choosing the interpolation points. Second-order dynamical systems are also considered in this paper, and the adaptive modified rational global Lanczos algorithm is applied to an equivalent state space model. Finally, some numerical examples will be given. [ABSTRACT FROM AUTHOR]

SUMMARY In 1907, Erhard Schmidt published a paper in which he introduced an orthogonalization algorithm that has since become known as the classical Gram-Schmidt process. Schmidt claimed that his procedure was essentially the same as an earlier one published by J. P. Gram in 1883. The Schmidt version was the first to become popular and widely used. An algorithm related to a modified version of the process appeared in an 1820 treatise by P. S. Laplace. Although related algorithms have been around for almost 200 years, it is the Schmidt paper that led to the popularization of orthogonalization techniques. The year 2007 marked the 100th anniversary of that paper. In celebration of that anniversary, we present a comprehensive survey of the research on Gram-Schmidt orthogonalization and its related QR factorization. Its application for solving least squares problems and in Krylov subspace methods are also reviewed. Software and implementation aspects are also discussed. Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper is concerned with the tight enclosure of matrix multiplication AB for two floating-point matrices A and B. The aim of this paper is to compute component-wise upper and lower bounds of the exact result C of the matrix multiplication AB by floating-point arithmetic. Namely, an interval matrix enclosing C is obtained. In this paper, new algorithms for enclosing C are proposed. The proposed algorithms are designed to mainly exploit the level 3 operations in BLAS. Although the proposed algorithms take around twice as much costs as a standard algorithm promoted by Oishi and Rump, the accuracy of the result by the proposed algorithms is better than that of the standard algorithm. At the end of this paper, we present numerical examples showing the efficiency of the proposed algorithms. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Tensor decompositions such as the canonical format and the tensor train format have been widely utilized to reduce storage costs and operational complexities for high‐dimensional data, achieving linear scaling with the input dimension instead of exponential scaling. In this paper, we investigate even lower storage‐cost representations in the tensor ring format, which is an extension of the tensor train format with variable end‐ranks. Firstly, we introduce two algorithms for converting a tensor in full format to tensor ring format with low storage cost. Secondly, we detail a rounding operation for tensor rings and show how this requires new definitions of common linear algebra operations in the format to obtain storage‐cost savings. Lastly, we introduce algorithms for transforming the graph structure of graph‐based tensor formats, with orders of magnitude lower complexity than existing literature. The efficiency of all algorithms is demonstrated on a number of numerical examples, and in certain cases, we demonstrate significantly higher compression ratios when compared to previous approaches to using the tensor ring format. [ABSTRACT FROM AUTHOR]

Preconditioners based on various multilevel extensions of two-level finite element methods (FEM) lead to iterative methods which have an optimal order computational complexity with respect to the size of the system. Such methods were first presented in Axelsson and Padiy (SIAM. J. Sci. Stat. Comp. 1990; 20:1807) and Axelsson and Vassilevski (Numer. Math. 1989; 56:157), and are based on (recursive) two-level splittings of the finite element space. The key role in the derivation of optimal convergence rate estimates is played by the constant γ in the so-called Cauchy–Bunyakowski–Schwarz (CBS) inequality, associated with the angle between the two subspaces of the splitting. It turns out that only existence of uniform estimates for this constant is not enough but accurate quantitative bounds for γ have to be found as well. More precisely, the value of the upper bound for γ∈(0,1) is part of the construction of various multilevel extensions of the related two-level methods. In this paper, an algebraic two-level preconditioning algorithm for second-order elliptic boundary value problems is constructed, where the discretization is done using Crouzeix–Raviart non-conforming linear finite elements on triangles. An important point to make is that in this case the finite element spaces corresponding to two successive levels of mesh refinements are not nested. To handle this, a proper two-level basis is considered, which enables us to fit the general framework for the construction of two-level preconditioners for conforming finite elements and to generalize the method to the multilevel case. The major contribution of this paper is the derived estimates of the related constant γ in the strengthened CBS inequality. These estimates are uniform with respect to both coefficient and mesh anisotropy. To our knowledge, the results presented in the paper are the first such estimates for non-conforming FEM systems. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Bramble et al. (Math. Comput. (2000); 69 (230) : 667–689) discussed the Uzawa type algorithms for iteratively solving nonsymmetric stable saddle point problems. In this paper, we consider the Uzawa type algorithms for iteratively solving generalized saddle point problems. Our main concern is how to accelerate the convergence of the inexact Uzawa type algorithms. The contributions of the paper are that a new non-linear Uzawa type algorithm is presented and its convergence is analysed. Applications to Navier–Stokes equations by mixed finite element discretization with an unstable pair of approximation spaces, i.e. Q1-P0 pair of approximation spaces, are discussed and the results of the numerical experiments of applying our new algorithm are presented. Copyright © 2003 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The use of matchings is a powerful technique for scaling and ordering sparse matrices prior to the solution of a linear system A x = b. Traditional methods such as implemented by the HSL software package MC64 use the Hungarian algorithm to solve the maximum weight maximum cardinality matching problem. However, with advances in the algorithms and hardware used by direct methods for the parallelization of the factorization and solve phases, the serial Hungarian algorithm can represent an unacceptably large proportion of the total solution time for such solvers. Recently, auction algorithms and approximation algorithms have been suggested as alternatives for achieving near-optimal solutions for the maximum weight maximum cardinality matching problem. In this paper, the efficacy of auction and approximation algorithms as replacements for the Hungarian algorithm is assessed in the context of sparse symmetric direct solvers when used in problems arising from a range of practical applications. High-cardinality suboptimal matchings are shown to be as effective as optimal matchings for the purposes of scaling. However, matching-based ordering techniques require that matchings are much closer to optimality before they become effective. The auction algorithm is demonstrated to be capable of finding such matchings significantly faster than the Hungarian algorithm, but our [ABSTRACT FROM AUTHOR]

Alternating least squares (ALS) is often considered the workhorse algorithm for computing the rank- R canonical tensor approximation, but for certain problems, its convergence can be very slow. The nonlinear conjugate gradient (NCG) method was recently proposed as an alternative to ALS, but the results indicated that NCG is usually not faster than ALS. To improve the convergence speed of NCG, we consider a nonlinearly preconditioned NCG (PNCG) algorithm for computing the rank- R canonical tensor decomposition. Our approach uses ALS as a nonlinear preconditioner in the NCG algorithm. Alternatively, NCG can be viewed as an acceleration process for ALS. We demonstrate numerically that the convergence acceleration mechanism in PNCG often leads to important pay-offs for difficult tensor decomposition problems, with convergence that is significantly faster and more robust than for the stand-alone NCG or ALS algorithms. We consider several approaches for incorporating the nonlinear preconditioner into the NCG algorithm that have been described in the literature previously and have met with success in certain application areas. However, it appears that the nonlinearly PNCG approach has received relatively little attention in the broader community and remains underexplored both theoretically and experimentally. Thus, this paper serves several additional functions, by providing in one place a concise overview of several PNCG variants and their properties that have only been described in a few places scattered throughout the literature, by systematically comparing the performance of these PNCG variants for the tensor decomposition problem, and by drawing further attention to the usefulness of nonlinearly PNCG as a general tool. In addition, we briefly discuss the convergence of the PNCG algorithm. In particular, we obtain a new convergence result for one of the PNCG variants under suitable conditions, building on known convergence results for non-preconditioned NCG. Copyright © 2014 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Summary: In this paper, we study the nearest stable matrix pair problem: given a square matrix pair (E,A), minimize the Frobenius norm of (ΔE,ΔA) such that (E+ΔE,A+ΔA) is a stable matrix pair. We propose a reformulation of the problem with a simpler feasible set by introducing dissipative Hamiltonian matrix pairs: A matrix pair (E,A) is dissipative Hamiltonian if A=(J−R)Q with skew‐symmetric J, positive semidefinite R, and an invertible Q such that QTE is positive semidefinite. This reformulation has a convex feasible domain onto which it is easy to project. This allows us to employ a fast gradient method to obtain a nearby stable approximation of a given matrix pair. [ABSTRACT FROM AUTHOR]

SUMMARY This paper introduces a new strategy for setting the regularization parameter when solving large-scale discrete ill-posed linear problems by means of the Arnoldi-Tikhonov method. This new rule is essentially based on the discrepancy principle, although no initial knowledge of the norm of the error that affects the right-hand side is assumed; an increasingly more accurate approximation of this quantity is recovered during the Arnoldi algorithm. Some theoretical estimates are derived in order to motivate our approach. Many numerical experiments performed on classical test problems as well as image deblurring problems are presented. Copyright © 2014 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY In a recent paper an algorithm for large-scale Tikhonov regularization in standard form called GKB-FP was proposed and numerically illustrated. In this paper, further insight into the convergence properties of this method is provided, and extensions to general-form Tikhonov regularization are introduced. In addition, as alternative to Tikhonov regularization, a preconditioned LSQR method coupled with an automatic stopping rule is proposed. Preconditioning seeks to incorporate smoothing properties of the regularization matrix into the computed solution. Numerical results are reported to illustrate the methods on large-scale problems. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY In this paper, a rapid iterative algorithm is proposed to find robust approximations for the inverse of nonsingular matrices. The analysis of convergence reveals that this high-order method possesses eighth-order convergence. The interesting point is that, this rate is attained using less number of matrix-by-matrix multiplications in contrast to the existing methods of the same type in the literature. The extension of the method for finding Moore-Penrose inverse of singular or rectangular matrices is also presented. Numerical comparisons will be given to show the applicability, stability and consistency of the new scheme by paying special attention on the computational time. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY This paper describes the development of explicit time stepping methods for linear PDEs that are specifically designed to cope with the stiffness of the system of ODEs that results from spatial discretization. As stiffness is caused by the contrasting behavior of coupled components of the solution, it is proposed to adopt a componentwise approach in which each coefficient of the solution in an appropriate basis is computed using an individualized approximation of the solution operator. This has been accomplished by Krylov subspace spectral (KSS) methods, which use techniques from 'matrices, moments and quadrature' to approximate bilinear forms involving functions of matrices via block Gaussian quadrature rules. These forms correspond to coefficients with respect to the chosen basis of the application of the solution operator of the PDE to the solution at an earlier time. In this paper, it is proposed to substantially enhance the efficiency of KSS methods through the prescription of quadrature nodes on the basis of asymptotic analysis of the recursion coefficients produced by block Lanczos iteration for each Fourier coefficient as a function of frequency. The potential of this idea is illustrated through numerical results obtained from the application of the modified KSS methods to diffusion equations and wave equations. Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY The aim of the nuclear norm minimization problem is to find a matrix that minimizes the sum of its singular values and satisfies some constraints simultaneously. Such a problem has received more attention largely because it is closely related to the affine rank minimization problem, which appears in many control applications including controller design, realization theory, and model reduction. In this paper, we first propose an exact version alternating direction method for solving the nuclear norm minimization problem with linear equality constraints. At each iteration, the method involves a singular value thresholding and linear matrix equations which are solved exactly. Convergence of the proposed algorithm is followed directly. To broaden the capacity of solving larger problems, we solve approximately the subproblem by an iterative method with the Barzilai-Borwein steplength. Some extensions to the noisy problems and nuclear norm regularized least-square problems are also discussed. Numerical experiments and comparisons with the state-of-the-art method FPCA show that the proposed method is effective and promising. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY Bootstrap algebraic multigrid (BAMG) is a multigrid-based solver for matrix equations of the form Ax = b. Its aim is to automatically determine the interpolation weights used in algebraic multigrid by locally fitting a set of test vectors that have been relaxed as solutions to the corresponding homogeneous equation, Ax = 0. This paper studies an improved form of BAMG, called relaxation-corrected bootstrap algebraic multigrid ( rBAMG), that involves adding scaled residuals of the test vectors to the least-squares equations. The basic rBAMG scheme was introduced in an earlier paper [1] and analyzed on a simple model problem. The purpose of the current paper is to further develop this algorithm by incorporating several new critical components and to systematically study its performance on an interesting model problem from quantum chromodynamics. Whereas the earlier paper introduced a new least-squares principle involving the residuals of the test vectors, a simple extrapolation scheme is developed here to accurately estimate the convergence factors of the evolving algebraic multigrid solver. Such a capability is essential to the effective development of a fast solver, and the approach introduced here is shown numerically to be much more effective than the conventional approach of just observing successive error reduction factors. Another component of the setup process developed here is an adaptive cycling process. This component assesses the effectiveness of the V-cycle constructed in the initial rBAMG phase by applying it to the homogeneous equation. When poor convergence is observed, the set of test vectors is enhanced with the resulting error, enabling the subsequent least-squares fit of interpolation to produce an improved V-cycle. A related component is the scaling and recombination Ritz process that targets the so-called weak approximation property in an attempt to reveal the important elements of these evolving error and test vector spaces. The aim of the numerical study documented here is to provide insight into the various design choices that arise in the development of an rBAMG algorithm. With this in mind, the results for quantum chromodynamics focus on the behavior of rBAMG in terms of the number of initial test vectors used, the number of relaxation sweeps applied to them, and the size of the target matrices. Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY For a Markov reward process, where upper and lower bounds for the transition rates and rewards are known, a new approach to bound the expected reward is presented. Based on a previous paper where sharp bounds have been defined for the problem, but only an inefficient and unstable algorithm is proposed, this paper presents algorithms to compute the bounds by interpreting the problem as a Markov Decision Process. In this way, the well known value and policy iteration algorithms can be adopted to compute reward bounds in a stable and fairly efficient way. Different numerical techniques are presented for computing the reward bounds. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY In this paper, we revisit the steady-state solution method for Markov Regenerative Processes (MRP) proposed in the work by German. This method solves the embedded Markov chain P of the MRP without storing the matrix P explicitly. We address three issues left open in German's Work: 1) the solution method is restricted to Power method; 2) it has been defined only for ergodic MRPs; and 3) no preconditioning is available to speed-up the computation. This paper discusses how to lift these limitations by extending the algorithm to preconditioned Krylov-subspace methods and by generalizing it to the non-ergodic case. An MRP-specific preconditioner is also proposed, which is built from a sparse approximation of the MRP matrix, computed via simulation. An experimental assessment of the proposed preconditioner is then provided. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Higher order finite element discretizations, although providing higher accuracy, are considered to be computationally expensive and of limited use for large-scale problems. In this paper, we have developed an efficient iterative solver for solving large-scale quadratic finite element problems. The proposed approach shares some common features with geometric multigrid methods but does not need structured grids to create the coarse problem. This leads to a robust method applicable to finite element problems discretized by unstructured meshes such as those from adaptive remeshing strategies. The method is based on specific properties of hierarchical quadratic bases. It can be combined with an algebraic multigrid (AMG) preconditioner or with other algebraic multilevel block factorizations. The algorithm can be accelerated by flexible Krylov subspace methods. We present some numerical results on the convection-diffusion and linear elasticity problems to illustrate the efficiency and the robustness of the presented algorithm. In these experiments, the performance of the proposed method is compared with that of an AMG preconditioner and other iterative solvers. Our approach requires less computing time and less memory storage. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Normal estimation is an important topic for processing point cloud data and surface reconstruction in computer graphics. In this paper we consider the problem of estimating normals for a (unknown) submanifold of a Euclidean space of codimension 1 from random points on the manifold. We propose a kernel-based learning algorithm in an unsupervised form of gradient learning. The algorithm can be implemented by solving a linear algebra problem. Error analysis is conducted under conditions on the true normals of the manifold and the sampling distribution. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper is motivated by some recent work of Fukuda, Ishiwata, Iwasaki, and Nakamura ( Inverse Problems 2009; :015007). We first design an algorithm for computing the eigenvalues of a specially structured matrix from the discrete Bogoyavlensky Lattice 2 (dBL2) system. A Lax representation for the dBL2 system is given in a matrix form. By considering the asymptotic behavior of dBL2 variables, some characteristic polynomials are then factorized. A new algorithm for computing the complex eigenvalues of a specially structured matrix is then introduced. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, we present a sparse linear discriminant analysis (LDA) algorithm for high-dimensional objects in subspaces. In high dimensional data, groups of objects often exist in subspaces rather than in the entire space. For example, in text data classification, groups of documents of different types are categorized by different subsets of terms. The terms for one group may not occur in the samples of other groups. In the new algorithm, we consider a LDA to calculate a weight for each dimension and use the weight values to identify the subsets of important dimensions in the discriminant vectors that categorize different groups. This is achieved by including the weight sparsity term in the objective function that is minimized in the LDA. We develop an iterative algorithm for computing such sparse and orthogonal vectors in the LDA. Experiments on real data sets have shown that the new algorithm can generate better classification results and identify relevant dimensions. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper concerns the LBM factorization of unsymmetric tridiagonal matrices, where L and M are unit lower triangular matrices and B is block diagonal with 1×1 and 2×2 blocks. In some applications, it is necessary to form this factorization without row or column interchanges while the tridiagonal matrix is formed. Bunch and Kaufman proposed a pivoting strategy without interchanges specifically for symmetric tridiagonal matrices, and more recently, Bunch and Marcia proposed pivoting strategies that are normwise backward stable for linear systems involving such matrices. In this paper, we extend these strategies to the unsymmetric tridiagonal case and demonstrate that the proposed methods both exhibit bounded growth factors and are normwise backward stable. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Nonlinear complementarity problem (NCP) is a wide class of problems. In this paper, some two-level additive Schwarz algorithms for NCPs with an M-function are developed and analyzed. The algorithms are proved to be convergent monotonically and can reach the solution of the problem within finite steps. They may also offer a possibility of making use of fast nonlinear solvers for solving the subproblems involved in the algorithms. Some preliminary numerical results are reported. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, we will discuss the geometric-based algebraic multigrid (AMG) method for two-dimensional linear elasticity problems discretized using quadratic and cubic elements. First, a two-level method is proposed by analyzing the relationship between the linear finite element space and higher-order finite element space. And then a geometric-based AMG method is obtained with the existing solver used as a solver on the first coarse level. The resulting AMG method is applied to some typical elasticity problems including the plane strain problem with jumps in Young's modulus. The results of various numerical experiments show that the proposed AMG method is much more robust and efficient than a classical AMG solver that is applied directly to the high-order systems alone. Moreover, we present the corresponding theoretical analysis for the convergence of the proposed AMG algorithms. These theoretical results are also confirmed by some numerical tests. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper is concerned with proving theoretical results related to the convergence of the conjugate gradient (CG) method for solving positive definite symmetric linear systems. Considering the inverse of the projection of the inverse of the matrix, new relations for ratios of the A-norm of the error and the norm of the residual are provided, starting from some earlier results of Sadok (Numer. Algorithms 2005; 40:201–216). The proofs of our results rely on the well-known correspondence between the CG method and the Lanczos algorithm. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper we consider an inverse problem for a damped vibration system from the noisy measured eigendata, where the mass, damping, and stiffness matrices are all symmetric positive-definite matrices with the mass matrix being diagonal and the damping and stiffness matrices being tridiagonal. To take into consideration the noise in the data, the problem is formulated as a convex optimization problem involving quadratic constraints on the unknown mass, damping, and stiffness parameters. Then we propose a smoothing Newton-type algorithm for the optimization problem, which improves a pre-existing estimate of a solution to the inverse problem. We show that the proposed method converges both globally and quadratically. Numerical examples are also given to demonstrate the efficiency of our method. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We study large-scale, continuous-time linear time-invariant control systems with a sparse or structured state matrix and a relatively small number of inputs and outputs. The main contributions of this paper are numerical algorithms for the solution of large algebraic Lyapunov and Riccati equations and linear-quadratic optimal control problems, which arise from such systems. First, we review an alternating direction implicit iteration-based method to compute approximate low-rank Cholesky factors of the solution matrix of large-scale Lyapunov equations, and we propose a refined version of this algorithm. Second, a combination of this method with a variant of Newton's method (in this context also called Kleinman iteration) results in an algorithm for the solution of large-scale Riccati equations. Third, we describe an implicit version of this algorithm for the solution of linear-quadratic optimal control problems, which computes the feedback directly without solving the underlying algebraic Riccati equation explicitly. Our algorithms are efficient with respect to both memory and computation. In particular, they can be applied to problems of very large scale, where square, dense matrices of the system order cannot be stored in the computer memory. We study the performance of our algorithms in numerical experiments. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Algebraic multigrid (AMG) is a powerful linear solver with attractive parallel properties. A parallel AMG method depends on efficient, parallel implementations of the coarse-grid selection algorithms and the restriction and prolongation operator construction algorithms. In the effort to effectively and quickly select the coarse grid, a number of parallel coarsening algorithms have been developed. This paper examines the behaviour of these algorithms in depth by studying the results of several numerical experiments. In addition, new parallel coarse-grid selection algorithms are introduced and tested. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper extends the weighted low rank approximation (WLRA) approach to linearly structured matrices. In the case of Hankel matrices with a special block structure, an equivalent unconstrained optimization problem is derived and an algorithm for solving it is proposed. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The past 13 years have seen the development of many algorithms for approximating matrix functions in O(N) time, where N is the basis size. These O(N) algorithms rely on assumptions about the spatial locality of the matrix function; therefore their validity depends very much on the argument of the matrix function. In this article I carefully examine the validity of certain O(N) algorithms when applied to Hamiltonians of disordered systems. I focus on the prototypical disordered system, the Anderson model. I find that O(N) algorithms for the density matrix function can be used well below the Anderson transition (i.e. in the metallic phase;) they fail only when the coherence length becomes large. This paper also includes some experimental results about the Anderson model's behaviour across a range of disorders. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Many popular solution methods for large discrete ill-posed problems are based on Tikhonov regularization and compute a partial Lanczos bidiagonalization of the matrix. The computational effort required by these methods is not reduced significantly when the matrix of the discrete ill-posed problem, rather than being a general nonsymmetric matrix, is symmetric and possibly indefinite. This paper describes new methods, based on partial Lanczos tridiagonalization of the matrix, that exploit symmetry. Computed examples illustrate that one of these methods can require significantly less computational work than available structure-ignoring schemes. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, we develop a fast regularized structured total least squares (RSTLS) algorithm for solving the basic deconvolution problem. The algorithm is based on a particular implementation of the generalized Schur algorithm. We apply the new algorithm on a deconvolution problem arising in a medical application in renography. By means of this example, we show that regularization in the structured total least squares framework yields more accurate results compared to other estimators. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper proposes and studies the performance of a preconditioner suitable for solving a class of symmetric positive definite systems, Apx=b, which we call lower rank extracted systems (LRES), by the preconditioned conjugate gradient method. These systems correspond to integral equations with convolution kernels defined on a union of many line segments in contrast to only one line segment in the case of Toeplitz systems. The p × p matrix, Ap, is shown to be a principal submatrix of a larger N × N Toeplitz matrix, AN. The preconditioner is provided in terms of the inverse of a 2N × 2N circulant matrix constructed from the elements of AN. The preconditioner is shown to yield clustering in the spectrum of the preconditioned matrix similar to the clustering results for iterative algorithms used to solve Toeplitz systems. The analysis also demonstrates that the computational expense to solve LRE systems is reduced to O(N log N). Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, we present a parallel Newton–Krylov–Schwarz (NKS)-based non-linearly implicit algorithm for the numerical solution of the unsteady non-linear multimaterial radiation diffusion problem in two-dimensional space. A robust solver technology is required for handling the high non-linearity and large jumps in material coefficients typically associated with simulations of radiation diffusion phenomena. We show numerically that NKS converges well even with rather large inflow flux boundary conditions. We observe that the approach is non-linearly scalable, but not linearly scalable in terms of iteration numbers. However, CPU time is more important than the iteration numbers, and our numerical experiments show that the algorithm is CPU-time-scalable even without a coarse space given that the mesh is fine enough. This makes the algorithm potentially more attractive than multilevel methods, especially on unstructured grids, where course grids are often not easy to construct. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper analyses a novel method for constructing preconditioners for diagonally dominant symmetric positive-definite matrices. The method discussed here is based on a simple idea: we construct M by simply dropping offdiagonal non-zeros from A and modifying the diagonal elements to maintain a certain row-sum property. The preconditioners are extensions of Vaidya's augmented maximum-spanning-tree preconditioners. The preconditioners presented here were also mentioned by Vaidya in an unpublished manuscript, but without a complete analysis. The preconditioners that we present have only O(n+t2) nonzeros, where n is the dimension of the matrix and 1⩽t⩽n is a parameter that one can choose. Their construction is efficient and guarantees that the condition number of the preconditioned system is O(n2/t2) if the number of nonzeros per row in the matrix is bounded by a constant. We have developed an efficient algorithm to construct these preconditioners and we have implemented it. We used our implementation to solve a simple model problem; we show the combinatorial structure of the preconditioners and we present encouraging convergence results. [ABSTRACT FROM AUTHOR]

Helmholtz equations with variable coefficients are known to be hard to solve both analytically and numerically. In this paper, we introduce a numerical multigrid solver for one-dimensional Helmholtz eigenvalue problems with periodic potentials and solutions. The solvers employ wave–ray methodology suggested by Brandt, Livshits for Helmholtz equations with constant coefficients. The paper concludes with numerical experiments and the discussion of future efforts for solving two-dimensional problems. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, we study a fully implicit parallel Newton–Krylov–Schwarz method (NKS) for solving the bidomain equations describing the electrical excitation process of the heart. NKS has been used successfully for many non-linear problems, but this is the first attempt to use this method for the bidomain model which consists of a system of time dependent partial differential equations of mixed type. Our experiments on parallel computers show that the method is scalable and robust with respect to many of the parameters in the bidomain model. In the outer layer of the algorithm, we use a non-linearly implicit backward Euler method to discretize the time derivative, and the resulting systems of large sparse non-linear equations are solved using an inexact Newton method. The Jacobian system required to solve in each Newton iteration is solved with a GMRES method preconditioned by a new component-wise restricted additive Schwarz preconditioner. The efficiency and robustness of the overall method depend heavily on what preconditioner we use. By comparing several preconditioners, we found our new restricted additive Schwarz method offers the best performance. Our parallel software is developed using the PETSc package of Argonne National Laboratory. Numerical results obtained on an IBM SP will be reported. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper presents the two‐parameter scaling memoryless Broyden–Fletcher–Goldfarb–Shanno (BFGS) method for solving a system of monotone nonlinear equations. The optimal values of the scaling parameters are obtained by minimizing the measure function involving all the eigenvalues of the memoryless BFGS matrix. The optimal values can be used in the analysis of the quasi‐Newton method for ill‐conditioned matrices. This algorithm can also be described as a combination of the projection technique and memoryless BGFS method. Global convergence of the method is provided. For validation and efficiency of the scheme, some test problems are computed and compared with existing results. [ABSTRACT FROM AUTHOR]

This paper is concerned with improving the empirical convergence speed of block‐coordinate descent algorithms for approximate nonnegative tensor factorization (NTF). We propose an extrapolation strategy in‐between block updates, referred to as heuristic extrapolation with restarts (HER). HER significantly accelerates the empirical convergence speed of most existing block‐coordinate algorithms for NTF, in particular for challenging computational scenarios, while requiring a negligible additional computational budget. [ABSTRACT FROM AUTHOR]

This paper extends the relationship between the author's operator trigonometry and convergence rates and other properties of important iterative methods. A new interesting trigonometric preconditioning lemma is given. The general relationship between domain decomposition methods and the operator trigonometry is established. A new basic conceptual link between sparse approximate inverse algorithms and the operator trigonometry is observed. A new underlying fundamental inherent trigonometry of the classical successive over-relaxation scheme is exposed. Some improved trigonometric interpretations of minimum residual schemes are mentioned. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Additive Schwarz preconditioned GMRES is a powerful method for solving large sparse linear systems of equations on parallel computers. The algorithm is often implemented in the Euclidean norm, or the discrete l2 norm, however, the optimal convergence result is available only in the energy norm (or the equivalent Sobolev H1 norm). Very little progress has been made in the theoretical understanding of the l2 behaviour of this very successful algorithm. To add to the difficulty in developing a full l2 theory, in this note, we construct explicit examples and show that the optimal convergence of additive Schwarz preconditioned GMRES in l2 cannot be obtained using the existing GMRES theory. More precisely speaking, we show that the symmetric part of the preconditioned matrix, which plays a role in the Eisenstat–Elman–Schultz theory, has at least one negative eigenvalue, and we show that the condition number of the best possible eigenmatrix that diagonalizes the preconditioned matrix, key to the Saad–Schultz theory, is bounded from both above and below by constants multiplied by h-1/2. Here h is the finite element mesh size. The results presented in this paper are mostly negative, but we believe that the techniques used in our proofs may have wide applications in the further development of the l2 convergence theory and in other areas of domain decomposition methods. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]