Search

In this paper we present an extension of Reusken's Lemma about the smoothing property of a multigrid method for solving non-symmetric linear systems of equations. One of the consequences of this extended lemma is the verification of the smoothing property for all damping factors ω ∈ (0,1). Additionally, a semi-iterative smoother is constructed which gives, in some sense, optimal smoothing rate estimates. [ABSTRACT FROM AUTHOR]

The special issue contains five papers from Foz2006—Congress on Mathematics and its Applications, held in Foz do Iguaçu, Brazil, on 7–11 August 2006, chaired by Yuan Jin Yun. The papers address preconditioners for saddle point problems, iterative methods, new family of penalty functions for optimization and their applications. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This special issue contains papers from the Thirteenth Copper Mountain Conference on Multigrid Methods, held in the Colorado Rocky Mountains on March 19–23, 2007, co-chaired by Van Henson and Joel Dendy. The papers address a variety of applications and cover a breadth of topics, ranging from theory to high-performance computing. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY Motivated by the increasing importance of large-scale networks typically modeled by graphs, this paper is concerned with the development of mathematical tools for solving problems associated with the popular graph Laplacian. We exploit its mixed formulation based on its natural factorization as product of two operators. The goal is to construct a coarse version of the mixed graph Laplacian operator with the purpose to construct two-level, and by recursion, a multilevel hierarchy of graphs and associated operators. In many situations in practice, having a coarse (i.e., reduced dimension) model that maintains some inherent features of the original large-scale graph and respective graph Laplacian offers potential to develop efficient algorithms to analyze the underlined network modeled by this large-scale graph. One possible application of such a hierarchy is to develop multilevel methods that have the potential to be of optimal complexity. In this paper, we consider general (connected) graphs and function spaces defined on its edges and its vertices. These two spaces are related by a discrete gradient operator, 'Grad' and its adjoint, ' − Div', referred to as (negative) discrete divergence. We also consider a coarse graph obtained by aggregation of vertices of the original one. Then, a coarse vertex space is identified with the subspace of piecewise constant functions over the aggregates. We consider the ℓ2-projection Q H onto the space of these piecewise constants. In the present paper, our main result is the construction of a projection π H from the original edge-space onto a properly constructed coarse edge-space associated with the edges of the coarse graph. The projections π H and Q H commute with the discrete divergence operator, that is, we have Div π H = Q H div. The respective pair of coarse edge-space and coarse vertex-space offer the potential to construct two-level, and by recursion, multilevel methods for the mixed formulation of the graph Laplacian, which utilizes the discrete divergence operator. The performance of one two-level method with overlapping Schwarz smoothing and correction based on the constructed coarse spaces for solving such mixed graph Laplacian systems is illustrated on a number of graph examples. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper we study the convergence of a multigrid method for the solution of a linear second-order elliptic equation, discretized by discontinuous Galerkin (DG) methods, and we give a detailed analysis of the convergence for different block-relaxation strategies. To complement an earlier paper where higher-order methods were studied, here we restrict ourselves to methods using piecewise linear approximations. It is well known that these methods are unstable if no additional interior penalty is applied. As for the higher-order methods, we find that point-wise block-relaxations give much better results than the classical cell-wise relaxations. Both for the Baumann–Oden and for the symmetric DG method, with a sufficient interior penalty, the block-relaxation methods studied (Jacobi, Gauss–Seidel and symmetric Gauss–Seidel) all make excellent smoothing procedures in a classical multigrid setting. Independent of the mesh size, simple MG cycles give convergence factors 0.2–0.4 per iteration sweep for the different discretizations studied. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY In this paper, we study the perturbation bound for the Perron vector of an mth-order n-dimensional transition probability tensor [ABSTRACT FROM AUTHOR]

In this paper the pole placement problem for singular systems via state feedback is studied. We give a complete solution to this problem for systems without row minimal indices. As a corollary, the eigenvalue assignment problem is solved for singular systems in the case they are regularizable. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, by generalizing the ideas of the (generalized) polar decomposition to the weighted polar decomposition and the unitarily invariant norm to the weighted unitarily invariant norm, we present some perturbation bounds for the generalized positive polar factor, generalized nonnegative polar factor, and weighted unitary polar factor of the weighted polar decomposition in the weighted unitarily invariant norm. These bounds extend the corresponding recent results for the (generalized) polar decomposition. In addition, we also give the comparison between the two perturbation bounds for the generalized positive polar factor obtained from two different methods. Copyright © 2008 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]

This paper deals with the solution of a non-linear ill-conditioned inverse problem arising in digital image registration. In the first part of the paper, we define the problem as the minimization of a regularized non-linear least-squares functional, which measures the image difference and smoothness of the transformation. We study inexact Newton methods for solving this problem, i.e. we linearize the functional around a current approximation and replace the Hessian by a suitable operator in order to obtain well-posed subproblems in each step of the iteration. These anisotropic subproblems are solved using a multigrid solver. Due to the anisotropy in the coefficients of the underlying equations, standard multigrid solvers suffer from poor convergence rates. We discuss modifications to the multigrid components, specifically to the smoothing procedure, the interpolation and the coarse grid correction. Numerical results that demonstrate the improvements obtained with these new components are given. Copyright © 2006 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Given the operator product BA in which both A and B are symmetric positive-definite operators, for which symmetric positive-definite operators C is BA symmetric positive-definite in the C inner product C? This question arises naturally in preconditioned iterative solution methods, and will be answered completely here. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The main focus of this paper is to suggest a domain decomposition method for finite element approximations of elliptic problems with anisotropic coefficients in domains consisting of anisotropic shape rectangles. The theorems on traces of functions from Sobolev spaces play an important role in studying boundary value problems of partial differential equations. These theorems are commonly used for a priori estimates of the stability with respect to boundary conditions, and also play very important role in constructing and investigating effective domain decomposition methods. The trace theorem for anisotropic rectangles with anisotropic grids is the main tool in this paper to construct domain decomposition preconditioners. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper compares the performance on linear systems of equations of three similar adaptive accelerating strategies for restarted GMRES. The underlying idea is to adaptively use spectral information gathered from the Arnoldi process. The first strategy retains approximations to some eigenvectors from the previous restart and adds them to the Krylov subspace. The second strategy also uses approximated eigenvectors to define a preconditioner at each restart. This paper designs a third new strategy which combines elements of both previous approaches. Numerical results show that this new method is both more efficient and more robust. © 1998 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Many processes in the sciences and in engineering are modelled by dynamical systems and-in discretized version-by nonlinear maps. To understand the often complicated dynamical behaviour it is a well established tool to use the concept of invariant manifolds of the system. In this way it is often possible to reduce the dimension of the system considerably. In this paper we propose a new method to calculate numerically invariant manifolds near fixed points of maps. We prove convergence of our procedure and provide an error estimation. Finally, the application of the method is illustrated by examples. [ABSTRACT FROM AUTHOR]

Estimating the number of eigenvalues located in a given interval of a large sparse Hermitian matrix is an important problem in certain applications, and it is a prerequisite of eigensolvers based on a divide-andconquer paradigm. Often, an exact count is not necessary, and methods based on stochastic estimates can be utilized to yield rough approximations. This paper examines a number of techniques tailored to this specific task. It reviews standard approaches and explores new ones based on polynomial and rational approximation filtering combined with a stochastic procedure. We also discuss how the latter method is particularly wellsuited for the FEAST eigensolver. [ABSTRACT FROM AUTHOR]

The pivoting strategy of Bunch and Marcia for solving systems involving symmetric indefinite tridiagonal matrices uses two different methods for solving 2 × 2 systems when a 2 × 2 pivot is chosen. In this paper, we eliminate this need for two methods by adding another criterion for choosing a 1 × 1 pivot. We demonstrate that all the results from the Bunch and Marcia pivoting strategy still hold. Copyright © 2006 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY In this paper, we construct and analyze a level-dependent coarse grid correction scheme for indefinite Helmholtz problems. This adapted multigrid (MG) method is capable of solving the Helmholtz equation on the finest grid using a series of MG cycles with a grid-dependent complex shift, leading to a stable correction scheme on all levels. It is rigorously shown that the adaptation of the complex shift throughout the MG cycle maintains the functionality of the two-grid correction scheme, as no smooth modes are amplified in or added to the error. In addition, a sufficiently smoothing relaxation scheme should be applied to ensure damping of the oscillatory error components. Numerical experiments on various benchmark problems show the method to be competitive with or even outperform the current state-of-the-art MG-preconditioned Krylov methods, for example, complex shifted Laplacian preconditioned flexible GMRES. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY In this paper, some important spectral characterizations of symmetric nonnegative tensors are analyzed. In particular, it is shown that a symmetric nonnegative tensor has the following properties: (i) its spectral radius is zero if and only if it is a zero tensor; (ii) it is weakly irreducible (respectively, irreducible) if and only if it has a unique positive (respectively, nonnegative) eigenvalue-eigenvector; (iii) the minimax theorem is satisfied without requiring the weak irreducibility condition; and (iv) if it is weakly reducible, then it can be decomposed into some weakly irreducible tensors. In addition, the problem of finding the largest eigenvalue of a symmetric nonnegative tensor is shown to be equivalent to finding the global solution of a convex optimization problem. Subsequently, algorithmic aspects for computing the largest eigenvalue of symmetric nonnegative tensors are discussed. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY This paper gives normwise and componentwise perturbation analyses for the Q-factor of the QR factorization of the matrix A with full column rank when A suffers from an additive perturbation. Rigorous perturbation bounds are derived on the projections of the perturbation of the Q-factor in the range of A and its orthogonal complement. These bounds overcome a serious shortcoming of the first-order perturbation bounds in the literature and can be used safely. From these bounds, identical or equivalent first-order perturbation bounds in the literature can easily be derived. When A is square and nonsingular, tighter and simpler rigorous perturbation bounds on the perturbation of the Q-factor are presented. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY Strang's proposal to use a circulant preconditioner for linear systems of equations with a Hermitian positive definite Toeplitz matrix has given rise to considerable research on circulant preconditioners. This paper presents an {ei φ}-circulant Strang-type preconditioner. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY This paper describes multilevel methods for the calculation of the stationary probability vector of large, sparse, irreducible Markov chains. In particular, several recently proposed significant improvements to the multilevel aggregation method of Horton and Leutenegger are described and compared. Furthermore, we propose a very simple improvement of that method using an over-correction mechanism. We also compare with more traditional iterative methods for Markov chains such as weighted Jacobi, two-level aggregation/disaggregation, and preconditioned stabilized biconjugate gradient and generalized minimal residual method. Numerical experiments confirm that our improvements lead to significant speedup, and result in multilevel methods that are competitive with leading iterative solvers for Markov chains. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper we construct some parallel relaxed multisplitting methods for solving consistent symmetric positive semidefinite linear systems, based on modified diagonally compensated reduction and incomplete factorizations. The semiconvergence of the parallel multisplitting method, relaxed multisplitting method and relaxed two-stage multisplitting method are discussed. The results generalize some well-known results for the nonsingular linear systems to the singular systems. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, an iterative solution method for a fourth-order accurate discretization of the Helmholtz equation is presented. The method is a generalization of that presented in (SIAM J. Sci. Comput. 2006; 27:1471–1492), where multigrid was employed as a preconditioner for a Krylov subspace iterative method. The multigrid preconditioner is based on the solution of a second Helmholtz operator with a complex-valued shift. In particular, we compare preconditioners based on a point-wise Jacobi smoother with those using an ILU(0) smoother, we compare using the prolongation operator developed by de Zeeuw in (J. Comput. Appl. Math. 1990; 33:1–27) with interpolation operators based on algebraic multigrid principles, and we compare the performance of the Krylov subspace method Bi-conjugate gradient stabilized with the recently introduced induced dimension reduction method, IDR(s). These three improvements are combined to yield an efficient solver for heterogeneous problems. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The paper investigates the inclusion intervals of matrix singular values. By employing the digraph of a matrix, some new inclusion intervals of matrix singular values are presented. These intervals are based mainly on the use of positive scale vectors and their intersections. Theoretic analysis and numerical examples show that these results improve and generalize some known results of Li et al. (Numer. Linear Algebra Appl. 2007; 14(2):115–128) and Kolotilina (J. Math. Sci. 2006; 137(3):4794–4800). Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The symmetric interior penalty (SIP) method on graded meshes and its fast solution by multigrid methods are studied in this paper. We obtain quasi-optimal error estimates in both the energy norm and the L2 norm for the SIP method, and prove uniform convergence of the W-cycle multigrid algorithm for the resulting discrete problem. The performance of these methods is illustrated by numerical results. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We consider linear matrix equations where the linear mapping is the sum of a standard Lyapunov operator and a positive operator. These equations play a role in the context of stochastic or bilinear control systems. To solve them efficiently one can fall back on known efficient methods developed for standard Lyapunov equations. In this paper, we describe a direct and an iterative method based on this idea. The direct method is applicable if the generalized Lyapunov operator is a low-rank perturbation of a standard Lyapunov operator; it is related to the Sherman–Morrison–Woodbury formula. The iterative method requires a stability assumption; it uses convergent regular splittings, an alternate direction implicit iteration as preconditioner, and Krylov subspace methods. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, a method for solving large-scale Sylvester equations is presented. The method is based on the sign function iteration and is particularly effective for Sylvester equations with factorized right-hand side. In this case, the solution will be computed in factored form as it is for instance required in model reduction. The hierarchical matrix format and the corresponding formatted arithmetic are integrated in the iteration scheme to make the method feasible for large-scale computations. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new class of frequency-filtering IBLU decompositions that use continued-fraction approximation for the diagonal blocks. This technique allows us to construct efficient frequency-filtering preconditioners for discretizations of elliptic partial differential equations on domains with non-trivial geometries. We prove theoretically for a class of model problems that the application of the proposed preconditioners leads to a convergence rate of up to 1-O(h1/4) of the CG iteration. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, we present efficient multigrid methods for systems of partial differential equations that are governed by a dominating grad–div operator. In particular, we show that distributive smoothing methods give multigrid convergence factors that are independent of problem parameters and of the mesh sizes in space and time. The applications range from model problems to secondary consolidation Biot's model. We focus on the smoothing issue and mainly solve academic problems on Cartesian-staggered grids. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper analyses a two-level preconditioning scheme for H(curl) bilinear forms. The scheme utilizes an auxiliary problem on a related mesh that is more amenable for constructing optimal order multigrid methods. More specifically, we analyse the case when the auxiliary mesh only approximately covers the original domain. The latter assumption is important since it allows for easy construction of nested multilevel spaces on regular auxiliary meshes. Numerical experiments in both two and three space dimensions illustrate the optimal performance of the method. Published in 2007 by John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We consider robust hierarchical splittings of finite element spaces related to non-conforming discretizations using Crouzeix–Raviart type elements. As is well known, this is the key to the construction of efficient two- and multilevel preconditioners. The main contribution of this paper is a theoretical and an experimental comparison of three such splittings. Our starting point is the standard method based on differences and aggregates (DA) as introduced in Blaheta et al. (Numer. Linear Algebra Appl. 2004; 11:309–326). On this basis we propose a more general (GDA) splitting, which can be viewed as the solution of a constraint optimization problem (based on certain symmetry assumptions). We further consider the locally optimal (ODA) splitting, which is shown to be equivalent to the first reduce (FR) method from Blaheta et al. (Numer. Linear Algebra Appl. 2004; 11:309–326). This means that both, the ODA and the FR splitting, generate the same subspaces, and thus the local constant in the strengthened Cauchy–Bunyakowski–Schwarz inequality is minimal for the FR (respectively ODA) splitting. Moreover, since the DA splitting corresponds to a particular choice in the parameter space of the GDA splitting, which itself is an element in the set of all splittings for which the ODA (or equivalently FR) splitting yields the optimum, we conclude that the chain of inequalities γ2FR⩽γ2GDA⩽γ2DA⩽3/4 holds independently of mesh and/or coefficient anisotropy. Apart from the theoretical considerations, the presented numerical results provide a basis for a comparison of these three approaches from a practical point of view. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, two new matrix-form iterative methods are presented to solve the least-squares problem:\documentclass{article}\usepackage[mathscr]{euscript}\usepackage{amssymb,amsbsy,rotating}\footskip=0pc\pagestyle{empty}\begin{document}\[ \min\limits_{X\in {\mathscr{S}}_1,Y\in {\mathscr{S}}_2}\|AXB+CYD-E\| \]\end{document} and matrix nearness problem: \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\[ \min\limits_{[X: Y]\in S_{XY}}\|[X: Y]-[\widetilde{X}:\widetilde{Y}]\| \] \end{document} where matrices $A\in R^{p\times n_1},B\in R^{n_2\times q},C\in R^{p\times m_1},D\in R^{m_2\times q},E\in R^{p\times q},\widetilde{X}\in R^{n_1\times n_2}$ and $\widetilde{Y}\in R^{m_1\times m_2}$ are given; 𝒮1 and 𝒮2 are the set of constraint matrices, such as symmetric, skew symmetric, bisymmetric and centrosymmetric matrices sets and SXY is the solution pair set of the minimum residual problem. These new matrix-form iterative methods have also faster convergence rate and higher accuracy than the matrix-form iterative methods proposed by Peng and Peng (Numer. Linear Algebra Appl. 2006; 13: 473–485) for solving the linear matrix equation AXB+CYD=E. Paige's algorithms, which are based on the bidiagonalization procedure of Golub and Kahan, are used as the framework for deriving these new matrix-form iterative methods. Some numerical examples illustrate the efficiency of the new matrix-form iterative methods. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Condition numbers play an important role in numerical analysis. Classical condition numbers are normwise: they measure the size of both input perturbations and output errors using norms. In this paper, we give explicit, computable expressions depending on the data, for the normwise condition numbers for the computation of the Moore–Penrose inverse as well as for the solutions of linear least-squares problems with full-column rank. Copyright © 2007 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, 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]

This paper is concerned with algebraic multigrid for finite element discretizations of the divgrad, curlcurl and graddiv equations on tetrahedral meshes with piecewise linear shape functions. First, an edge, face and volume prolongator are derived from an arbitrary partition of unity nodal prolongator for a tetrahedral fine mesh, using the formulas for edge, face and volume elements. This procedure can be repeated recursively. The implied coarse topology and the normalization of the prolongators are analysed. It is proved that the range spaces of the nodal prolongator and of the derived edge, face and volume prolongators form a discrete de Rham complex if these prolongators have full rank. It is shown that on simplicial meshes, the constructed edge prolongator is a generalization of the Reitzinger–Schöberl prolongator. The derived edge and face prolongators are applied in an algebraic multigrid method for the curlcurl and graddiv equations, and numerical results are presented. 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]

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]

We consider strategies to construct optimal order two- and multilevel hierarchical preconditioners for linear systems as arising from the finite element discretization of self-adjoint second order elliptic problems using non-conforming Crouzeix–Raviart linear elements. In this paper we utilize the hierarchical decompositions, derived in a previous work by the same authors (Numerical Linear Algebra with Applications 2004; 11:309–326) and provide a further analysis of these decompositions in order to assure robustness with respect to anisotropy. Finally, we show how to construct both multiplicative and additive versions of the algebraic multilevel iteration preconditioners and show robustness and optimal order convergence estimates. 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]

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]

In this paper, a new method for the computation of the infimum for a large class of continuous-time H∞ optimal control problem by state feedback is presented. The main ingredients of the new method include three generalized eigenvalue problems whose coefficient matrices are from a condensed form of the given system. This condensed form is computed using only orthogonal transformations which can be implemented via a numerically stable way. The superiority of the new method over the existing one given in Chen (H∞Control and its Applications, Chapter 5. Springer: Berlin, 1997) is verified by some numerical examples. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Let x* denote the solution of a linear least-squares problem of the form $$ {\rm minimize} \quad \|A{\bf x}-{\bf b}\|^{2}_{2}$$ where A is a full rank m × n matrix, m > n. Let r*=b - Ax* denote the corresponding residual vector. In most problems one is satisfied with accurate computation of x*. Yet in some applications, such as affine scaling methods, one is also interested in accurate computation of the unit residual vector r*/∥r*∥2. The difficulties arise when ∥r*∥2 is much smaller than ∥b∥2. Let &xcirca; and &rcirc; denote the computed values of x* and r*, respectively. Let ℇdenote the machine precision in our computations, and assume that &rcirc; is computed from the equality &rcirc; =b-A&xcirca;. Then, no matter how accurate &xcirca; is, the unit residual vector û =&rcirc;/∥&rcirc;∥2 contains an error vector whose size is likely to exceed ℇ∥b∥2/∥r*∥2. That is, the smaller ∥r*∥2 the larger the error. Thus although the computed unit residual should satisfy ATû=0, in practice the size of ∥ATû∥2 is about ℇ∥A∥2∥b∥2/∥r*∥2. The methods discussed in this paper compute a residual vector, &rcirc;, for which ∥AT&rcirc;∥2 is not much larger than ℇ∥A∥2∥&rcirc;∥2. Numerical experiments illustrate the difficulties in computing small residuals and the usefulness of the proposed safeguards. Copyright © 2004 John Wiley & Sons, Ltd. [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]

This paper studies the use of a generalized hierarchical basis transformation at each level of a multilevel block factorization. The factorization may be used as a preconditioner to the conjugate gradient method, or the structure it sets up may be used to define a multigrid method. The basis transformation is performed with an averaged piecewise constant interpolant and is applicable to unstructured elliptic problems. The results show greatly improved convergence rate when the transformation is applied for solving sample diffusion and elasticity problems. The cost of the method, however, grows and can get very high with the number of non-zeros per row. 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]

This paper suggests a new method, called AINV-A, for constructing sparse approximate inverse preconditioners for positive-definite matrices, which can be regarded as a modification of the AINV method proposed by Benzi and Túma. Numerical results on SPD test matrices coming from different applications demonstrate the robustness of the AINV-A method and its superiority to the original AINV approach. Copyright © 2001 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, we present a normwise perturbation theory for the regular generalized eigenproblem Ax = λBx, when λ is a semi-simple and finite eigenvalue, which departs from the classical analysis with the chordal norm [9]. A backward error and a condition number are derived for a choice of flexible measure to represent independent perturbations in the matrices A and B. The concept of optimal backward error associated with an eigenvalue only is also discussed. © 1998 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]