Search

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]

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]

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 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]

SUMMARY The strong stability of a symplectic matrix is investigated from algorithmic and numerical viewpoints using a theory developed by S.K. Godunov. This theory is based on a different formulation of the Krein-Gelfand-Lidskii characterization of strong stability, better suited for numerical calculations. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY Inexact algorithms allow certain operations (typically matrix-vector products or certain function evaluations) to be performed inexactly, either out of necessity or deliberately, in view of trading accuracy for speed. We review recent findings that show the impact of the inexact approach in the uniformization and generalized minimal residual (GMRES) methods when computing the transient, stationary, and cumulative solutions of realistic Markov chain problems of large size arising from computer systems and biochemical reactions. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Numerically reliable algorithms to compute the periodic non-negative definite stabilizing solutions of the periodic differential Riccati equation (PRDE) and discrete-time periodic Riccati equation (DPRE) are proposed. For the numerical solution of PRDEs, a new multiple shooting-type algorithm is developed to compute the periodic solutions in an arbitrary number of time moments within one period by employing suitable discretizations of the continuous-time problems. In contrast to single shooting periodic generator methods, the multiple shooting-type methods have the main advantage of being able to address problems with larger periods. Three methods are discussed to solve DPREs. Two of the methods represent extensions of the periodic QZ algorithm to non-square periodic pairs, whereas the third method represents an extension of a quotient-product swapping and collapsing ‘fast’ algorithm. All proposed approaches are completely general, being applicable to periodic Riccati equations with time-varying dimensions as well as with singular weighting matrices. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We study Davidson-type subspace eigensolvers. Correction equations of Jacobi-Davidson and several other schemes are reviewed. New correction equations are derived. A general correction equation is constructed, existing correction equations may be considered as special cases of this general equation. The main theme of this study is to identify the essential common ingredient that leads to the efficiency of a diverse form of Davidson-type methods. We emphasize the importance of the approximate Rayleigh-quotient-iteration direction. [ABSTRACT FROM AUTHOR]

We solve the problem of minimizing the distance from a given matrix to the cone of symmetric and diagonally dominant matrices with positive diagonal (SDD+). Using the extreme rays of the polar cone we project onto the supporting hyperplanes of the faces of SDD+ and then, applying the cyclic Dykstra's algorithm, we solve the problem. Similarly, using the extreme rays of SDD+ we characterize the projection onto the polar cone, which also allows us to obtain the projection onto SDD+ by means of the orthogonal decomposition theorem for convex cones. In both cases the symmetry and the sparsity pattern of the given matrix are preserved. Preliminary numerical experiments indicate that the polar approach is a promising one. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We present robust and asymptotically optimal iterative methods for solving 2D anisotropic elliptic equations with strongly jumping coefficients, where the direction of anisotropy may change sharply between adjacent subdomains. The idea of a stable preconditioning for the Schur complement matrix is based on the use of an exotic non-conformal coarse mesh space and on a special clustering of the edge space components according to the anisotropy behavior. Our method extends the well known BPS interface preconditioner [2] to the case of anisotropic equations. The technique proposed also provides robust solvers for isotropic equations in the presence of degenerate geometries, in particular, in domains composed of thin substructures. Numerical experiments confirm efficiency and robustness of the algorithms for the complicated problems with strongly varying diffusion and anisotropy coefficients as well as for the isotropic diffusion equations in the ‘brick and mortar’ structures involving subdomains with high aspect ratios. Copyright © 1999 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The frontal method is a variant of Gaussian elimination that has been widely used since the mid 1970s. In the innermost loop of the computation the method exploits dense linear algebra kernels, which are straightforward to vectorize and parallelize. This makes the method attractive for modern computer architectures. However, unless the matrix can be ordered so that the front is never very large, frontal methods can require many more floating-point operations for factorization than other approaches. We are interested in matrices that have a highly asymmetric structure. We use the idea of a row graph of an unsymmetric matrix combined with a variant of Sloan's profile reduction algorithm to reorder the rows. We also look at applying the spectral method to the row graph. Numerical experiments performed on a range of practical problems illustrate that our proposed MSRO and hybrid MSRO row ordering algorithms yield substantial reductions in the front sizes and, when used with a frontal solver, significantly enhance its performance both in terms of the factorization time and storage requirements. Copyright © 1999 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We present experiments with various solvers for large sparse generalized symmetric matrix eigenvalue problems. These problems occur in the computation of a few of the lowest frequencies of standing electromagnetic waves in resonant cavities with the finite element method. The solvers investigated are (1) subspace iteration, (2) block Lanczos algorithm, (3) implicitly restarted Lanczos algorithm and (4) Jacobi–Davidson algorithm. The experiments have been conducted on a Hewlett-Packard Exemplar S-Class system. Copyright © 1999 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

A modification is presented of the classical O(n²) algorithm of Trench for the direct solution of Toeplitz systems of equations. The Trench algorithm is stable for symmetric matrices that are positive definite, but can be unstable for the indefinite cast (and for general matrices). Our modification permits extension of the algorithm to compute approximate inverses of indefinite symmetric Toeplitz matrices, for which the unmodified algorithm breaks down when principal submatrices are singular. As a preconditioner, the approximate inverse has an advantage that only matrix-vector multiplications are required for the solution of a linear system, without forward and backward solves. The approximate inverse so obtained can be sufficiently accurate, moreover, that, when it is used as a preconditioner for the applications investigated, subsequent iteration may not even be necessary. Numerical results are given for several test matrices. The perturbation to the original matrix that defines the modification is related to a perturbation in a quantity generated in the Trench algorithm; the associated stability of the Trench algorithm is discussed. [ABSTRACT FROM AUTHOR]

We consider the problem of computing Uk = Qk Uk-1 (where U0 is given) in finite precision (∈ M = machine precision) where U0 and the Qi are known to be unitary. The problem is that Ûk, the computed product may not be unitary, so one applies an O(n2) orthogonalizing step after each multiplication to (a) prevent Ûk from drifting too far from the set of of unitary matrices (b) prevent Ûk from drifting too far from Uk the true product. Our main results are 1. Scaling the rows to have unit length after each multiplication (the cheapest of the algorithms considered) is usually as good as any other method with respect to either of the criteria (a) or (b). 2. A new orthogonalization algorithm that guarantees that the distance of Ûk (k = 1, 2 .... ) to the set of unitary matrices is bounded by n3.5∈M for any choice of Qi. [ABSTRACT FROM AUTHOR]

An algorithm for pre- or post-multiplication of a matrix by a plane rotation, using only three vector saxpy operations instead of the four vector operations usually considered necessary, is described. No auxiliary storage for overwriting is required. The method is shown to be numerically stable. [ABSTRACT FROM AUTHOR]

We show that certain multisplitting iterative methods based on overlapping blocks yield faster convergence than corresponding nonoverlapping block iterations, provided the coefficient matrix is an M-matrix. This result can be used to compare variants of the waveform relaxation algorithm for solving initial value problems. The methods under consideration use the same discretization technique, but are based on multisplittings with different overlaps. Numerical experiments on the Intel 1PSC/860 hypercube are included. [ABSTRACT FROM AUTHOR]