Search

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

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

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]

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]

This paper describes a method to avoid the singular problem at the "S-control" algorithm. The "S-control" is proposed to determine the correct operating state in any bia polar transistor network (BTN). Each diode of the Ebers-Moll model is replaced with a directional switch called an S-branch which has "on" and "off" states. The switch status is changed by the S-control algorithm. How- ever, the matrix singular problem occurs in the process of the S-control. The singular matrix is formed by a cutset of only current sources or a loop of only voltage sources. The singular problem is solved by the sign- discrimination method by which the sign of each node voltage is judged by the introduction of small immittances in cutset (loop) of only current (voltage) sources formed in process of the S-control. The S-control algorithm will be continued to obtain the next switch state unless the limit cycle is not generated. [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]

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]

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]

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]

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]

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]

We consider algebraic multilevel preconditioning methods based on the recursive use of a 2 × 2 block incomplete factorization procedure in which the Schur complement is approximated by a coarse grid matrix. As is well known, for discrete second-order elliptic PDEs, optimal convergence properties are proved for such basic two-level schemes under mild assumptions on the PDE coefficients, but their recursive use in a simple V-cycle algorithm does not generally lead to optimal order convergence. In the present paper, we analyse the combination of these techniques with a smoothing procedure much the same as the one used in standard multigrid algorithms, except that smoothing is not required on the finest grid. Theoretical results prove optimal convergence properties for the V-cycle under an assumption similar to the ‘approximation property’ of the classical multigrid convergence theory. On the other hand, numerical experiments made on both 2D and 3D problems show that the condition number is close to that of the two-level method. Further, the method appears robust in the presence of discontinuity and anisotropy, even when the material interfaces are not aligned with the coarse grid. Copyright © 1999 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The implicit Cholesky algorithm has been developed by several authors during the last 10 years but under different names. We identify the algorithm with a special version of Rutishauser's LR algorithm. Intermediate quantities in the transformation furnish several attractive approximations to the smallest singular value. The paper extols the advantages of using shifts with the algorithm. The nonorthogonal transformations improve accuracy. [ABSTRACT FROM AUTHOR]

In this paper, we demonstrate the scalability of the Reduced System Conjugate Gradient (RSCG) algorithm on distributed memory architectures. We present speed-up results obtained on the Intel iPSC/860 that compare one-, two-, and three-dimensional decompositions of the domain lot both positive definite and positive semidefinite test problems. We develop a model for the RSCG algorithm to analyze computational and communication costs. The model is validated using experimental data and then used to examine and predict behavior of the RSCG algorithm as a function of architecture parameters including communication latency and transmission times and memory access costs. [ABSTRACT FROM AUTHOR]

The boundary residual method is a powerful technique for solving EM boundary-value problems. This technique produces matrices difficult to solve using many of the standard numerical techniques. This paper discusses lesser-known numerical aspects of this method, and it shows efficient and well-conditioned methods to solve both the homogeneous' and non-homogeneous boundary residual problem. [ABSTRACT FROM AUTHOR]

Torrance [4] has proposed a "new" approach to finding an initial solution of a linear programming problem for use in conjunction with the dual simplex algorithm. The purpose of this note is to comment on two aspects of that paper. Firstly, Torrance's method is not new at all, but !`as proposed in 1958 by Wagner. Secondly, the method can be implemented much more efficiently than Torrance suggests. [ABSTRACT FROM AUTHOR]

The discrete cosine transform (DCT) is one of the discrete orthogonal transformations, for which fast computation algorithms are known. It has the property that the transformed sequence has most of the energy in the lower-order components, and is utilized widely in feature extraction and high-efficiency coding. The following methods have been known as the fast-cosine transform (FCT): (1) Computation is performed through the fast-Fourier transform (FFT) with real sequence; (2) Computation is made by decomposing the matrix representing DCT into sparse factors. In those methods, approximately N log2N real multiplications and (3/2)N log2N real additions are required for computation of DCT for N = 2v points. The FCT proposed in this paper differs from those methods in the following points. The DCT is represented by a finite series of Chebyshev polynomials. The order of the series is successively halved utilizing the successive factorization of Chebyshev polynomial, finally arriving at DCT values. By this method, (1/2) N log2N real multiplications and (3/2) N log2N real additions suffice to calculate the DCT for N points: the number of multiplications is halved, compared with the previous methods. The method is similar, in its structure, to FFT with radix 2, which leads to the feature that the programming is simple. [ABSTRACT FROM AUTHOR]

Split Levinson and Schur algorithms for the inversion of symmetric Toeplitz matrices are presented that work, in contrast to previous algorithms, without additional conditions like strong non-singularity. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The paper presents an algorithm for computing the asymptotic Fisher information matrix of a possibly seasonal single-input single-output (SISO) time-series model. That matrix is a block matrix whose elements are basically integrals of rational functions over the oriented unit circle. The procedure makes use of the autocovariance or the cross-covariance function of two autoregressive processes based on the same noise. The algorithm also works when the input variable is omitted, the case of a seasonal ARMA model. [ABSTRACT FROM AUTHOR]

A new iterative scheme is described for the solution of large linear systems of equations with a matrix of the form A = ρU + &zetaI, where ρ and ζ are constants, U is a unitary matrix and I is the identity matrix. We show that for such matrices a Krylov subspace basis can be generated by recursion formulas with few terms. This leads to a minimal residual algorithm that requires little storage and makes it possible to determine each iterate with fairly little arithmetic work. This algorithm provides a model for iterative methods for non-Hermitian linear systems of equations, in a similar way to the conjugate gradient and conjugate residual algorithms. Our iterative scheme illustrates that results by Faber and Manteuffel [3,4] on the existence of conjugate gradient algorithms with short recurrence relations, and related results by Joubert and Young [13], can be extended. [ABSTRACT FROM AUTHOR]

Methods related to the mathematical domain deal with the direct processing of the initial matrix T without any analytic transformation process or procedure for approximating the initial data, such as factorial or clustering methods do. These two last methods need to replace the initial T by a square matrix I x I (for the objects) or J x J (for the variables) before to be applied. These direct methods have been introduced to answer concerns slightly different from those used to process with square matrices.

The method of elastic multibody systems is frequently used to describe the dynamical behavior of the mechanical subsystems in multi-physics simulations. One important issue for the simulation of elastic multibody systems is the error-controlled reduction of the flexible body's degrees of freedom. By the use of second order frequency-weighted Gramian matrix based reduction techniques the distribution of the loads is taken into account a-priori and very accurate models can be obtained within a predefined frequency range and even a-priori error bounds are available. However, the calculation of the frequency-weighted Gramian matrices requires high computational effort. Hence, appropriate approximation schemes have to be used to find the dominant eigenspace of these matrices. In the current contribution, the matrix integral needed for calculating the Gramian matrices is approximated by quadratures using integral kernel snapshots. The number and location of these snapshots have a strong influence on the reduction results. Sophisticated snapshot selection methods based on Greedy algorithms from the reduced basis methods are used to construct the optimal location of snapshot frequencies. The method can be viewed as an automatic determination of optimal frequency weighting and as an adaptive learning of quadrature rules. One ingredient of Greedy algorithms is the need of error measures. To gain computational advantage two different error estimators are derived and used in the Greedy algorithm instead of the absolute or relative error. [ABSTRACT FROM AUTHOR]

We propose a new data representation for octrees and kd-trees that improves upon memory size and algorithm speed of existing techniques. While pointerless approaches exploit the regular structure of the tree to facilitate efficient data access, their memory footprint becomes prohibitively large as the height of the tree increases. Pointerbased trees require memory consumption proportional to the number of tree nodes, thus exploiting the typical sparsity of large trees. Yet, their traversal is slowed by the need to follow explicit pointers across the different levels. Our solution is a pointerless approach that represents each tree level with its own matrix, as opposed to traditional pointerless trees that use only a single vector. This novel data organization allows us to fully exploit the tree's regular structure and improve the performance of tree operations. By using a sparse matrix data structure we obtain a representation that is suited for sparse and dense trees alike. In particular, it uses less total memory than pointer-based trees even when the data set is extremely sparse. We show how our approach is easily implemented on the GPU and illustrate its performance in typical visualization scenarios. [ABSTRACT FROM AUTHOR]

Recently, a number of variants of the approximate minimum degree algorithm have been proposed that aim to efficiently order symmetric matrices containing some dense rows. We compare the performance of these variants on a range of problems and highlight their potential limitations. This leads us to propose a new variant that offers both speed and robustness. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We devise a fast fraction-free algorithm for the computation of the triangular factorization of Bernstein–Bezoutian matrices with entries over an integral domain. Our approach uses the Bareiss fraction-free variant of Gaussian elimination, suitably modified to take into account the structural properties of Bernstein–Bezoutian matrices. The algorithm can be used to solve problems in algebraic geometry that arise in computer aided geometric design and computer graphics. In particular, an example of the application of this algorithm to the numerical computation of the intersection points of two planar rational Bézier curves is presented. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Fast algorithms, based on the unsymmetric look-ahead Lanczos and the Arnoldi process, are developed for the estimation of the functional Φ(ƒ)=uTƒ(A) v for fixed u, v and A, where A∈ℜn×n is a large-scale unsymmetric matrix. Numerical results are presented which validate the comparable accuracy of both approaches. Although the Arnoldi process reaches convergence more quickly in some cases, it has greater memory requirements, and may not be suitable for especially large applications. Copyright © 2003 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We present a fast algorithm for computing the QR factorization of Cauchy matrices with real nodes. The algorithm works for almost any input matrix, does not require squaring the matrix, and fully exploits the displacement structure of Cauchy matrices. We prove that, if the determinant of a certain semiseparable matrix is non-zero, a three term recurrence relation among the rows or columns of the factors exists. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this work, we apply the ideas of domain decomposition and multi-grid methods to PDE-based eigenvalue problems represented in two equivalent variational formulations. To find the lowest eigenpair, we use a “subspace correction” framework for deriving the multiplicative algorithm for minimizing the Rayleigh quotient of the current iteration. By considering an equivalent minimization formulation proposed by Mathew and Reddy, we can use the theory of multiplicative Schwarz algorithms for non-linear optimization developed by Tai and Espedal to analyse the convergence properties of the proposed algorithm. We discuss the application of the multiplicative algorithm to the problem of simultaneous computation of several eigenfunctions also formulated in a variational form. Numerical results are presented. Copyright © 2001 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Non-stationary parallel multisplitting iterative methods are introduced for the solution of almost linear systems. A non-stationary parallel algorithm based on the AOR-type methods and its extension to asynchronous models are considered. Convergence properties of the synchronous and asynchronous versions of these methods are studied for M-matrices and H-matrices. Furthermore, computational results about these methods on a distributed memory multiprocessor, which illustrate the performance of the algorithms studied, are discussed. Copyright © 1999 John Wiley & Sons, Ltd. [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]

Rank revealing factorizations are used extensively in signal processing in connection with, for example, linear prediction and signal subspace algorithms. We present an algorithm for computing rank revealing QR factorizations of low-rank matrices. The algorithm produces tight upper and lower bounds for all the largest singular values, thus making it particularly useful for treating rank deficient problems by means of subset selection, truncated QR, etc. The algorithm is similar in spirit to an algorithm suggested earlier by Chan for matrices with a small nullity, and it can also be considered as an extension of ordinary column pivoting. [ABSTRACT FROM AUTHOR]

A convex hexahedral TLM mesh of arbitrary shape is presented and the transmission-line matrix method extended to any non-orthogonal configuration. The novel mesh constitutes a natural generalization of Johns' condensed node. The associated TLM process is analysed and reconstructed as a genuine finite difference time-domain algorithm. Nodal S-parameters are derived from discretized Maxwell's equations and canonical stability criteria yield the TLM timestep. Unitarity is discussed and energy conservation confirmed in the non-conductive case. A given block-diagonal representation of the S-matrix restrains processing time per node and iteration within the range of traditional methods. The shortcomings of the rigid classical grid, as the need for inaccurate staircasing approximations, are, however, ruled out. Our analysis takes advantage of the recently developed propagator integral approach. [ABSTRACT FROM AUTHOR]

We present a numerical example illustrating that the deflation procedure in Francis's implicitly shifted QR algorithm can be improved by a deflation criteria based on the QR decomposition of the upper Hessenberg matrix. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]