Search

We derive a new representation for the exact convergence factor of classical two-level and two-grid preconditioners. Based on this result, we establish necessary and sufficient conditions for constructing the components of efficient algebraic multigrid (AMG) methods. The relation of the sharp estimate to the classical two-level hierarchical basis methods is discussed as well. Lastly, as an application, we give an optimal two-grid convergence proof of a purely algebraic ‘window’-AMG method. Published in 2005 by John Wiley & Sons, Ltd. [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]

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]

A preconditioning methodology for an iterative solution of discrete stress analysis problems based on a space decomposition and subspace correction framework is analysed in this paper. The principle idea of our approach is a decomposition of a global discrete system into the series of subproblems each of which correspond to the different Cartesian co-ordinates of the solution (displacement) vector. This enables us to treat the matrix subproblems in a segregated way. A host of well-established scalar solvers can be employed for the solution of subproblems. In this paper we constrain ourselves to an approximate solution using the scalar algebraic multigrid (AMG) solver, while the subspace correction is performed either in block diagonal (Jacobi) or block lower triangular (Gauss–Seidel) fashion. The preconditioning methodology is justified theoretically for the case of the block-diagonal preconditioner using Korn's inequality for estimating the ratio between the extremal eigenvalues of a preconditioned matrix. The effectiveness of the AMG-based preconditioner is tested on stress analysis 3D model problems that arise in microfabrication technology. The numerical results, which are in accordance with theoretical predictions, clearly demonstrate the superiority of a component decomposition AMG preconditioner over the standard ILU preconditioner, even for the problems with a relatively small number of degrees of freedom. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Recently the hp version of the finite element method, in which adaptivity occurs in both the size, h, of the elements and in the order, p, of the approximating piecewise polynomials, has received increasing attention. It is desirable to combine this optimal order discretization method with an optimal order algebraic solution method like multigrid. An intriguing notion is to use the values of p as the levels of a multilevel method. In this paper we present such a method, known as hp-multigrid, for high-order finite elements and hp-adaptive grids. We present a survey of the development of p-multigrid and hp-multigrid, define an hp-multigrid algorithm based on the p-hierarchical basis for the p levels and h-hierarchical basis for an h-multigrid solution of the p=1 ‘coarse grid’ equations, and present numerical convergence results using hp-adaptive grids. The numerical results suggest that the method has a convergence rate of \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}$\frac{1}{2}$\end{document} for Poisson's equation. Published in 2010 by John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, we consider the nonsymmetric algebraic Riccati equation arising in transport theory. An important feature of this equation is that its minimal positive solution can be obtained via computing the minimal positive solution of a vector equation. We apply the Newton–Shamanskii method to solve the vector equation. Convergence analysis shows that the sequence of vectors generated by the Newton–Shamanskii method is monotonically increasing and converges to the minimal positive solution of the vector equation. Numerical experiments show that the Newton–Shamanskii method is feasible and effective, and outperforms the Newton method. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

A matrix with positive row sums and all its off-diagonal elements bounded above by their corresponding row averages is called a B-matrix by J. M. Peña in References (SIAM J. Matrix Anal. Appl. 2001; 22:1027–1037) and (Numer. Math. 2003; 95:337–345). In this paper, it is generalized to more extended matrices—MB-matrices, which is proved to be a subclass of the class of P-matrices. Subsequently, we establish relationships between defined and some already known subclasses of P-matrices (see, References SIAM J. Matrix Anal. Appl. 2000; 21:67–78; Linear Algebra Appl. 2004; 393:353–364; Linear Algebra Appl. 1995; 225:117–123). As an application, some subclasses of P-matrices are used to localize the real eigenvalues of a real matrix. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Let A be an n × n symmetric matrix of bandwidth 2m + 1. The matrix need not be positive definite. In this paper we will present an algorithm for factoring A which preserves symmetry and the band structure and limits element growth in the factorization. With this factorization one may solve a linear system with A as the coefficient matrix and determine the inertia of A, the number of positive, negative, and zero eigenvalues of A. The algorithm requires between 1/2nm2 and 5/4nm2 multiplications and at most (2m + 1)n locations compared to non-symmetric Gaussian elimination which requires between nm2 and 2nm2 multiplications and at most (3m + 1)n locations. Our algorithm reduces A to block diagonal form with 1 × 1 and 2 × 2 blocks on the diagonal. When pivoting for stability and subsequent transformations produce non-zero elements outside the original band, column/row transformations are used to retract the bandwidth. To decrease the operation count and the necessary storage, we use the fact that the correction outside the band is rank-1 and invert the process, applying the transformations that would restore the bandwidth first, followed by a modified correction. This paper contains an element growth analysis and a computational comparison with LAPACKs non-symmetric band routines and the Snap-back code of Irony and Toledo. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The electrical activity in the heart is governed by the bidomain equations. In this paper, we analyse an order optimal method for the algebraic equations arising from the discretization of this model. Our scheme is defined in terms of block Jacobi or block symmetric Gauss–Seidel preconditioners. Furthermore, each block in these methods is based on standard preconditioners for scalar elliptic or parabolic partial differential equations (PDEs). Such preconditioners can be realized in terms of multigrid or domain decomposition schemes, and are thus readily available by applying ‘off-the-shelves’ software. Finally, our theoretical findings are illuminated by a series of numerical experiments. Copyright © 2006 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]

In this paper the definition of semiseparable matrices is investigated. Properties of the frequently used definition and the corresponding representation by generators are deduced. Corresponding to the class of tridiagonal matrices another definition of semiseparable matrices is introduced preserving the nice properties dual to the class of tridiagonal matrices. Several theorems and properties are included showing the viability of this alternative definition. Because of the alternative definition, the standard representation of semiseparable matrices is not satisfying anymore. The concept of a representation is explicitly formulated and a new kind of representation corresponding to the alternative definition is given. It is proved that this representation keeps all the interesting properties of the generator representation. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper we consider solving Hermitian Toeplitz systems Tnx=b by using the preconditioned conjugate gradient (PCG) method. Here the Toeplitz matrices Tn are assumed to be generated by a non-negative continuous 2π-periodic function ƒ, i.e. Tn=𝒯n[ƒ]. It was proved in (Linear Algebra Appl. 1993; 190:181) that if ƒ is positive then the spectrum of 𝒯n[1/ƒ]𝒯n[ƒ] is clustered around 1. We prove that the trigonometric polynomial qn(s) (s⩾2, cf. (2) and (3)) converges to 1/ƒ uniformly as n→∞ under the condition that 1/ƒ is in Wiener class. It follows that the computational cost of the PCG method can be reduced by replacing 1/ƒ with qN(2), where Nn when ƒ has finite zeros of even orders. We prove that with our preconditioners, the preconditioned matrix has spectrum clustered around 1. It follows that the PCG methods converge very fast when applied to solve the preconditioned systems. Numerical results are given to demonstrate the efficiency of our preconditioners. Copyright © 2004 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]

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]

This paper studies the possibility of combining interior point strategy with a steepest descent method when solving convex programming problems, in such a way that the convergence property of the interior point method remains valid but many iterations do not request the solution of a system of equations. Motivated by this general idea, we propose a hybrid algorithm which combines a primal–dual potential reduction algorithm with the use of the steepest descent direction of the potential function. The $O(\sqrt{n}\left|{\ln {\epsilon}} \right|)$ complexity of the potential reduction algorithm remains valid but the overall computational cost can be reduced. Our numerical experiments are also reported. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, we construct new ω-circulant preconditioners for non-Hermitian Toeplitz systems, where we allow the generating function of the sequence of Toeplitz matrices to have zeros on the unit circle. We prove that the eigenvalues of the preconditioned normal equation are clustered at 1 and that for (N, N)-Toeplitz matrices with spectral condition number 𝒪(Nα) the corresponding PCG method requires at most 𝒪(N log2N) arithmetical operations. If the generating function of the Toeplitz sequence is a rational function then we show that our preconditioned original equation has only a fixed number of eigenvalues which are not equal to 1 such that preconditioned GMRES needs only a constant number of iteration steps independent of the dimension of the problem. Numerical tests are presented with PCG applied to the normal equation, GMRES, CGS and BICGSTAB. In particular, we apply our preconditioners to compute the stationary probability distribution vector of Markovian queuing models with batch arrival. Copyright © 2001 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We consider the GMRES(s), i.e. the restarted GMRES with restart s for the solution of linear systems Ax = b with complex coefficient matrices. It is well known that the GMRES(s) applied on a real system is convergent if the symmetric part of the matrix A is positive definite. This paper introduces sufficient conditions implying the convergence of a restarted GMRES for a more general class of non-Hermitian matrices. For real systems these conditions generalize the known result initiated as above. The discussion after the main theorem concentrates on the question of how to find an integer j such that the GMRES(s) converges for all s ≥ j. Additional properties of GMRES obtained by derivation of the main theorem are presented in the last section. Copyright © 2000 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to present an algorithm for matrix multiplication based on a formula discovered by Pan [7]. For matrices of order up to 10 000, the nearly optimum tuning of the algorithm results in a rather clear non-recursive one- or two-level structure with the operation count comparable to that of the Strassen algorithm [9]. The algorithm takes less workspace and has better numerical stability as compared to the Strassen algorithm, especially in Winograd's modification [2]. Moreover, its clearer and more flexible structure is potentially more suitable for efficient implementation on modern supercomputers. Copyright © 1999 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In certain inverse problems it is useful to be able to compute solutions which arc, in some sense, as simple as possible. For example, one may wish to compute solutions which are piecewise constant and with as few discontinuities as possible. Such solutions are suited to describe models, e.g., geological layers, where the coarse structure is more important than the fine structure. A natural generalization of piecewise constant functions is piecewise polynomial solutions. In this paper we present a new algorithm which is capable of computing solutions that are piecewise polynomials, without having to specify a priori the positions of the break points between the polynomial pieces. [ABSTRACT FROM AUTHOR]

This paper investigates the relations between the structured backward error (SBE) and the partial structured backward error (P-SBE), and the partial backward error (P-BE) and the P-SBE for a computed solution to general Toeplitz system. In particular, we show in some cases the P-SBE for general Toeplitz system is usually a good estimate of the SBE. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper presents a new algebraic extension of the Rayleigh quotient multigrid (RQMG) minimization algorithm to compute the smallest eigenpairs of a symmetric positive definite pencil (A, M). Earlier versions of RQMG minimize the Rayleigh quotient over a hierarchy of geometric grids. We replace the geometric mesh information with the algebraic information defined by an algebraic multigrid preconditioner. At each level, we minimize the Rayleigh quotient with a block preconditioned algorithm. Numerical experiments illustrate the efficiency of this new algorithm to compute several eigenpairs. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The paper deals with the application of the restricted-denominator rational Krylov method, recently discussed in (BIT 2004; 44(3):595–615; SIAM J. Sci. Comput. 2005; 27:1438–1457), to the computation of the action of the so-called ϕ-functions, which play a fundamental role in several modern exponential integrators. The analysis here presented is devoted in particular to the construction of error estimates of easy practical use. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, some necessary and sufficient conditions for the existence of the positive definite solutions for the matrix equation X + A*X-αA = Q with α ∈ (0, ∞) are given. Iterative methods to obtain the positive definite solutions are established and the rates of convergence of the considered methods are obtained. Copyright © 2006 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, some optimal inclusion intervals of matrix singular values are discussed in the set ΩA of matrices equimodular with matrix A. These intervals can be obtained by extensions of the Gerschgorin-type theorem for singular values, based only on the use of positive scale vectors and their intersections. Theoretic analysis and numerical examples show that upper bounds of these intervals are optimal in some cases and lower bounds may be non-trivial (i.e. positive) when PA is a H-matrix, where P is a permutation matrix, which improves the conjecture in Reference (Linear Algebra Appl 1984; 56:105-119). Copyright © 2006 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, two direct algorithms for solving the two-sided obstacle problem with an M-matrix are presented. The algorithms are well defined and have polynomial computational complexity. Copyright © 2006 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The paper develops Newton's method of finding multiple eigenvalues with one Jordan block and corresponding generalized eigenvectors for matrices dependent on parameters. It computes the nearest value of a parameter vector with a matrix having a multiple eigenvalue of given multiplicity. The method also works in the whole matrix space (in the absence of parameters). The approach is based on the versal deformation theory for matrices. Numerical examples are given. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Algebraic multigrid (AMG) is an efficient algorithm for solving certain types of large, sparse linear systems. For solving very large problems with AMG it becomes necessary to use parallel algorithms. Coarse grid selection algorithms such as CLJP were created to parallelize the setup phase of AMG. For some problems, such as those discretized on structured meshes, CLJP tends to select coarse grids with more nodes than alternative coarsening algorithms. In this paper, the cause for the selection of too many coarse nodes by CLJP is examined, and a new technique which lowers the operator complexities generated by CLJP is introduced. To validate the new method, the modified CLJP is compared to other coarsening algorithms for large-scale problems. Copyright © 2006 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper presents a new efficient way to implement multigrid algorithms on adaptively refined grids. To cope with todays demands in high-performance computing, we cannot do without such highly sophisticated numerical methods. But if we do not implement them very carefully, we lose a lot of efficiency in terms of memory usage: using trees for the storage of hierarchical multilevel data causes a large amount of non-local (in terms of the physical memory space) data accesses, and often requires the storage of pointers to neighbours to allow the evaluation of discrete operators (difference stencils, restrictions, interpolations, etc.). The importance of this problem becomes clear if we remember that storage and not the CPUs is the bottleneck on modern computers. We established a cache-oblivious and storage-minimizing algorithm based on the concept of space-tree grids combined with a cell-oriented operator evaluation, a linear ordering of grid cells along a space-filling curve, and a sophisticated construction of linearly processed data structures for vertex data. In this context, we could show that the implementation of a dynamically adaptive F-cycle is, first, very natural and, second, does not cause any overhead in terms of storage usage and access as adaptivity and multilevel data do not disturb the linear processing order of our data structures. Copyright © 2006 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, we present a new approach to the parallelization of algebraic multigrid (AMG), i.e. to the parallel coarse-grid selection in AMG. Our approach involves (almost) no special treatment of processor subdomain boundaries and hence avoids a number of drawbacks of other AMG parallelization techniques. The key idea is to select an appropriate (local) coarse grid on each processor from a set of admissible grids such that the composed coarse grid forms a suitable coarse grid for the whole domain, i.e. there is no need for a special boundary treatment. To this end, we first construct multiple equivalent coarse grids on each processor subdomain. In a second step we then select exactly one grid per processor by a graph clustering technique. The results of our numerical experiments clearly indicate that this approach results in coarse grids of high quality which are very close to those obtained with sequential AMG. Furthermore, the operator and grid complexities of our parallel AMG are mostly smaller than those obtained by other parallel AMG methods, whereas the scale-up behaviour of the proposed algorithm is similar to that of other parallel AMG techniques. However a significant improvement with respect to the speed-up performance is achieved. Copyright © 2006 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Structured matrix algebras ℒ and a generalized BFGS-type iterative scheme have been recently investigated to introduce low-complexity quasi-Newton methods, named ℒQN, for solving general (non-structured) minimization problems. In this paper we introduce the ℒkQN methods, which exploit ad hoc algebras at each step. Since the structure of the updated matrices can be modified at each iteration, the new methods can better fit the Hessian matrix, thereby improving the rate of convergence of the algorithm. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Several representations for the interpolating polynomial exist: Lagrange, Newton, orthogonal polynomials, etc. Each representation is characterized by some basis functions. In this paper we investigate the transformations between the basis functions which map a specific representation to another. We show that for this purpose the LU- and the QR-decomposition of the Vandermonde matrix play a crucial role. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The paper deals with Krylov methods for approximating functions of matrices via interpolation. In this frame residual smoothing techniques based on quasi-kernel polynomials are considered. Theoretical results as well as numerical experiments illustrate the effectiveness of our approach. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The pivoted QLP decomposition, introduced by Stewart, represents the first two steps in an algorithm which approximates the SVD. If A is an m-by-n matrix, the matrix A∏0 is first factored as A∏0 = QR, and then the matrix RT∏1 is factored as RT∏1 = PLT, resulting in A = Q∏1LPT∏0T, with Q and P orthogonal, L lower-triangular, and ∏0 and ∏1 permutation matrices. The Q and P matrices provide approximations of the left and right singular subspaces, and the diagonal elements of L are excellent approximations of the singular values of A. Stewart observed that pivoting is not necessary in the second step, allowing one to efficiently truncate the decomposition, computing only the first few columns of R and L and choosing the stopping point dynamically. In this paper, we demonstrate that this truncating actually works by extending our theory for the complete pivoted QLP decomposition (UCLA CAM Report # 02-29, 2002). In particular, say there is a gap between σk and σk+1, and partition the matrix L into diagonal blocks L11 and L22 and off-diagonal block L21, where L11 is k-by-k. If we compute only the block L11, the convergence of (σj(L11)-1 - σj-1)/σj-1 for j = 1,...,k are all quadratic in the gap ratio σk+1/σk. Hence, if the gap ratio is small, as it usually is when A has numerical rank k (independent of m and n), then all of the singular values are likely to be well approximated. This truncated pivoted QLP decomposition can be computed in 𝒪(mnk) time, making it ideal for accurate SVD approximations of low-rank matrices. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The computation of the minimal positive solution of a non-symmetric algebraic Riccati equation arising in transport theory is considered. It was shown in (SIAM J Matrix Anal Appl, submitted) that this can be done via only computing the minimal positive solution of a vector equation, which is derived from special form of the solutions of the Riccati equation and by exploitation of the special structure of the coefficient matrices of the Riccati equation. In this paper, the Newton method is developed for the vector equation. The Newton method is more simple and efficient than the corresponding Newton method directly for original Riccati equation and can preserve the form that any solution of the Riccati equation must satisfy. Combination of the simple iteration and the Newton iteration is also considered. Numerical examples are given. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper we present some new absolute and relative perturbation bounds of eigenvalues of normal matrices. The bounds depend upon the closeness of perturbed matrices to normal matrices and improve those previous results (Duke Math. J. 1953; 20:37–39, Linear Algebra Appl. 1996; 246:215–223). Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper we discuss some linear algebra issues concerning the implementation of blended implicit methods (J. Comput. Appl. Math. 2000; 116:41–62, Appl. Numer. Math. 2002; 42:29–45, J. Comput. Appl. Math. 2004; 164–165:145–158, In Recent Trends in Numerical Analysis, Trigiante D (ed.), Nova Science Publication Inc.: New York, 2001; 81–105) for the numerical solution of ODEs. In particular, we describe the strategies, used in the numerical code BiM (J. Comput. Appl. Math. 2004; 164–165:145–158), for deciding whether re-evaluating the Jacobian and/or the factorization involved in the non-linear splitting for solving the discrete problem. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The symmetric Sinc–Galerkin method developed by Lund (Math. Comput. 1986; 47:571–588), when applied to second-order self-adjoint boundary value problems on d dimensional rectangular domains, gives rise to an N × N positive definite coefficient matrix which can be viewed as the sum of d Kronecker products among d - 1 real diagonal matrices and one symmetric Toeplitz-plus-diagonal matrix. Thus, the resulting coefficient matrix has a strong structure so that it can be advantageously used in solving the discrete system. The main contribution of this paper is to present and analyse a multigrid method for these Sinc–Galerkin systems. In particular, we show by numerical examples that the solution of a discrete symmetric Sinc–Galerkin system can be obtained in an optimal way only using O(N log N) arithmetic operations. Numerical examples concerning one- and two-dimensional problems show that the multigrid method is practical and efficient for solving the above symmetric Sinc–Galerkin linear system. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

For decades considerable efforts have been exerted to resolve the inverse eigenvalue problem for non-negative matrices. Yet fundamental issues such as the theory of existence and the practice of computation remain open. Recently, it has been proved that, given an arbitrary (n–1)-tuple ℒ = (λ2,...,λn) ∈ ℂn–1 whose components are closed under complex conjugation, there exists a unique positive real number ℛ(ℒ), called the minimal realizable spectral radius of ℒ, such that the set {λ1,...,λn} is precisely the spectrum of a certain n × n non-negative matrix with λ1 as its spectral radius if and only if λ1 ⩾ ℛ(ℒ). Employing any existing necessary conditions as a mode of checking criteria, this paper proposes a simple bisection procedure to approximate the location of ℛ(ℒ). As an immediate application, it offers a quick numerical way to check whether a given n-tuple could be the spectrum of a certain non-negative matrix. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Many very large Markov chains can be modelled efficiently as stochastic automata networks (SANs). A SAN is composed of individual automata which, for the most part, act independently, requiring only infrequent interaction. SANs represent the generator matrix Q of the underlying Markov chain compactly as the sum of Kronecker products of smaller matrices. Thus, storage savings are immediate. The benefit of a SAN's compact representation, known as the descriptor, is often outweighed by its tendency to make analysis of the underlying Markov chain tough. While iterative or projections methods have been used to solve the system πQ=0, the time until these methods converge to the stationary solution π is still unsatisfactory. SAN's compact representation has made the next logical research step of preconditioning thorny. Several preconditioners for SANs have been proposed and tested, yet each has enjoyed little or no success. Encouraged by the recent success of approximate inverses as preconditioners, we have explored their potential as SAN preconditioners. One particularly relevant finding on approximate inverse preconditioning is the nearest Kronecker product approximation discovered by Pitsianis and Van Loan. In this paper, we extend the nearest Kronecker product technique to approximate the Q matrix for an SAN with a Kronecker product, A1 ⊗A2. … ⊗AN. Then, we take M = A1-1 ⊗A2-1⊗ … ⊗AN-1 as our SAN NKP preconditioner. [ABSTRACT FROM AUTHOR]

In this paper, an eigenvalue analysis of the SIMPLE preconditioning for incompressible flow is presented. Some formulations have been set up to characterize the spectrum of the preconditioned matrix. This leads to a generalized eigenvalue problem. The generalized eigenvalue problem is investigated. Some eigenvalue bounds and the estimation for the spectral condition number in the symmetric case are given. Numerical tests are reported to illustrate the theoretical discussions. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The partial pole assignment (PPA) problem is the one of reassigning a few unwanted eigenvalues of a control system by feedback to suitably chosen ones, while keeping the remaining large number of eigenvalues unchanged. The problem naturally arises in modifying dynamical behaviour of the system. The PPA has been considered by several authors in the past for standard state–space systems and for quadratic matrix polynomials associated with second-order systems. In this paper, we consider the PPA for a cubic matrix polynomial arising from modelling of a vibrating system with aerodynamics effects and derive explicit formulas for feedback matrices in terms of the coefficient matrices of the polynomial. Our results generalize those of a quadratic matrix polynomial by Datta et al. (Linear Algebra Appl. 1997;257: 29) and is based on some new orthogonality relations for eigenvectors of the cubic matrix polynomial, which also generalize the similar ones reported in Datta et al. (Linear Algebra Appl. 1997;257: 29) for the symmetric definite quadratic pencil. Besides playing an important role in our solution for the PPA, these orthogonality relations are of independent interests, and believed to be an important contribution to linear algebra in its own right. Copyright © 2003 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In a recent work, the author introduced a robust multilevel incomplete factorization algorithm using spanning trees of matrix graphs (Proceedings of the 1999 International Conference on Preconditioning Techniques for Large Sparse Matrix Problems in Industrial Applications, Hubert H. Humphrey Center, University of Minnesota, 1999, 251–257). Based on this idea linear and non-linear algebraic multilevel iteration (AMLI) methods are investigated in the present paper. In both cases, the preconditioner is constructed recursively from the coarsest to finer and finer levels. The considered W-cycles only need diagonal solvers on all levels and additionally evaluate a second-degree matrix polynomial (linear case), or, perform ν inner GCG-type iterations (non-linear case) on every other level. This involves the same type of preconditioner for the corresponding Schur complement. The non-linear variant has the additional benefit of being free from any method parameters to be estimated. Based on the same type of approximation property similar convergence rates are obtained for linear and non-linear AMLI, even for a very small number ν of inner iterations, e.g. ν =2,3. The presented methods are robust with respect to anisotropy and discontinuities in the coefficients of the PDEs and can also be applied to unstructured-grid problems. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

To precondition large sparse linear systems resulting from the discretization of second-order elliptic partial differential equations, many recent works focus on the so-called algebraic multilevel methods. These are based on a block incomplete factorization process applied to the system matrix partitioned in hierarchical form. They have been shown to be both robust and efficient in several circumstances, leading to iterative solution schemes of optimal order of computational complexity. Now, despite the procedure is essentially algebraic, previous works focus generally on a specific context and consider schemes that use classical grid hierarchies with characteristic mesh sizes h,2h,4h, etc. Therefore, these methods require some extra information besides the matrix of the linear system and lack of robustness in some situations where semi-coarsening would be desirable. In this paper, we develop a general method that can be applied in a black box fashion to a wide class of problems, ranging from 2D model Poisson problems to 3D singularly perturbed convection–diffusion equations. It is based on an automatic coarsening process similar to the one used in the AMG method, and on coarse grid matrices computed according to a simple and cheap aggregation principle. Numerical experiments illustrate the efficiency and the robustness of the proposed approach. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper defines topology relations of elements treated as overlapping lists of nodes. In particular, the element topology makes use of element faces, element vertices and boundary faces which coincide with the actual (geometrical) faces, vertices and boundary faces in the case of true finite elements. The element topology is used in an agglomeration algorithm to produce agglomerated elements (a non-overlapping partition of the original elements) and their topology is then constructed, thus allowing for recursion. The main part of the algorithms is based on operations on Boolean sparse matrices and the implementation of the algorithms can utilize any available (parallel) sparse matrix format. Applications of the sparse matrix element topology to AMGe (algebraic multigrid for finite element problems), including elementwise constructions of coarse non-linear finite element operators are outlined. An algorithm to generate a block nested dissection ordering of the nodes for generally unstructured finite element meshes is given as well. The coarsening of the element topology is illustrated on a number of fine-grid unstructured triangular meshes. Published in 2002 by John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This is the second part of a trilogy on parallel solution of the linear elasticity problem. We consider the plain case of the problem with isotropic material, including discontinuous coefficients, and with homogeneous Dirichlet boundary condition. The discretized problem is solved by the preconditioned conjugate gradient (pcg) method. In the first part of the trilogy block-diagonal preconditioners based on the separate displacement component part of the elasticity equations were analysed. The preconditioning systems were solved by the pcg-method, i.e. inner iterations were performed. As preconditioner, we used modified incomplete factorization MIC(0), where possibly the element matrices were modified in order to give M-matrices, i.e. in order to guarantee the existence of the MIC(0) factorization. In the present paper, the second part, full block incomplete factorization preconditioners are presented and analysed. In order to avoid inner/outer iterations we also study a variant of the block-diagonal method and of the full block method, where the matrices of the inner systems are just replaced by their MIC(0)-factors. A comparison is made between the various methods with respect to rate of convergence and work per unknown. The fastest methods are implemented by message passing utilizing the MPI system. In the third part of the trilogy, we will focus on the use of higher-order finite elements. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper presents an algebraic multigrid method for the efficient solution of the linear system arising from a finite element discretization of variational problems in H0(curl,Ω). The finite element spaces are generated by Nédélec's edge elements. A coarsening technique is presented, which allows the construction of suitable coarse finite element spaces, corresponding transfer operators and appropriate smoothers. The prolongation operator is designed such that coarse grid kernel functions of the curl-operator are mapped to fine grid kernel functions. Furthermore, coarse grid kernel functions are ‘discrete’ gradients. The smoothers proposed by Hiptmair and Arnold, Falk and Winther are directly used in the algebraic framework. Numerical studies are presented for 3D problems to show the high efficiency of the proposed technique. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The modified Gram–Schmidt (MGS) orthogonalization process—used for example in the Arnoldi algorithm—often constitutes the bottleneck that limits parallel efficiencies. Indeed, a number of communications, proportional to the square of the problem size, are required to compute the dot-products. A block formulation is attractive but it suffers from potential numerical instability. In this paper, we address this issue and propose a simple procedure that allows the use of a block Gram—Schmidt algorithm while guaranteeing a numerical accuracy close to that of MGS. The main idea is to determine the size of the blocks dynamically. The main advantages of this dynamic procedure are two-fold: first, high performance matrix–vector multiplications can be used to decrease the execution time. Next, in a parallel environment, the number of communications is reduced. Performance comparisons with the alternative Iterated CGS also show an improvement for a moderate number of processors. Copyright © 2000 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Given convex scattered data in R3 we consider the constrained interpolation problem of finding a smooth, minimal Lp-norm (1 < p < ∞) interpolation network that is convex along the edges of an associated triangulation. In previous work the problem has been reduced to the solution of a nonlinear system of equations. In this paper we formulate and analyse a Newton-type algorithm for solving the corresponding type of systems. The correctness of the application of the proposed method is proved and its superlinear (in some cases quadratic) convergence is shown. Copyright © 2000 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The convergence behaviour of a number of algorithms based on minimizing residual norms over Krylov subspaces is not well understood. Residual or error bounds currently available are either too loose or depend on unknown constants that can be very large. In this paper we take another look at traditional as well as alternative ways of obtaining upper bounds on residual norms. In particular, we derive inequalities that utilize Chebyshev polynomials and compare them with standard inequalities. Copyright © 2000 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper the Navier-Stokes equations are discretized by semi-implicit schemes and the resulting symmetric or non-symmetric systems of linear equations are treated. A number of solvers for solving generally non-symmetric systems of linear equations are tested in order to find the optimal one. Copyright © 1999 John Wiley & Sons, Ltd. Copyright © 1999 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]