An efficient two-step iterative method for solving a class of complex symmetric linear systems

In this paper, a new two-step iterative method called the two-step parameterized (TSP) iteration method for a class of complex symmetric linear systems is developed. We investigate its convergence conditions and derive the quasi-optimal parameters which minimize the upper bound of the spectral radius of the iteration matrix of the TSP iteration method. Meanwhile, some more practical ways to choose iteration parameters for the TSP iteration method are proposed. Furthermore, comparisons of the TSP iteration method with some existing ones are given, which show that the upper bound of the spectral radius of the TSP iteration method is smaller than those of the modified Hermitian and skew-Hermitian splitting (MHSS), the preconditioned MHSS (PMHSS), the combination method of real part and imaginary part (CRI) and the parameterized variant of the fixed-point iteration adding the asymmetric error (PFPAE) iteration methods proposed recently. Inexact version of the TSP iteration (ITSP) method and its convergence properties are also presented. Numerical experiments demonstrate that both TSP and ITSP are effective and robust when they are used either as linear solvers or as matrix splitting preconditioners for the Krylov subspace iteration methods and they have comparable advantages over some known ones for the complex symmetric linear systems.     

Hierarchical LU Decomposition-based Preconditioners for BEM

The adaptive cross approximation method can be used to efficiently approximate stiffness matrices arising from boundary element applications by hierarchical matrices. In this article an approximative LU decomposition in the same format is presented which can be used for preconditioning the resulting coefficient matrices efficiently. If the LU decomposition is computed with high precision, it may even be used as a direct yet efficient solver.     

Adaptive Recompression of -Matrices for BEM

The efficient treatment of dense matrices arising, e.g., from the finite element discretisation of integral operators requires special compression techniques. In this article, we use a hierarchical low-rank approximation, the so-called -matrix, that approximates the dense stiffness matrix in admissible blocks (corresponding to subdomains where the underlying kernel function is smooth) by low rank matrices. The low rank matrices are assembled by the ACA+ algorithm, an improved variant of the well-known ACA method. We present an algorithm that can determine a coarser block structure that minimises the storage requirements (enhanced compression) and speeds up the arithmetic (e.g., inversion) in the -matrix format. This coarse approximation is done adaptively and on-the-fly to a given accuracy such that the matrix is assembled with minimal storage requirements while keeping the desired approximation quality. The benefits of this new recompression technique are demonstrated by numerical examples.     

An Alternative Algorithm for a Sliding Window ULV Decomposition

The ULV decomposition (ULVD) is an important member of a class of rank-revealing two-sided orthogonal decompositions used to approximate the singular value decomposition (SVD). The ULVD can be modified much faster than the SVD. When modifiying the ULVD, the accurate computation of the subspaces is required in certain time varying applications in signal processing. In this paper, we present an updating algorithm which is suitable for large scaled matrices of low rank and as effective as alternatives. The algorithm runs in O(n²) time.     

On convergence of splitting iteration methods for non-Hermitian positive-definite linear systems

A new splitting iteration method is presented for the system of linear equations when the coefficient matrix is a non-Hermitian positive-definite matrix. The spectral radius, the optimal parameter, and some norm properties of the iteration matrix for the new method are discussed in detail. Based on these results, the new method is convergent under reasonable conditions for any non-Hermitian positive-definite linear system. Finally, the numerical examples show that the new method is more effective than the Hermitian and skew-Hermitian splitting iterative (or positive-definite and skew-Hermitian splitting iterative) method in central processing unit time.     

On the Convergence Acceleration of Slowly Convergent Sums Involving Oscillating Terms

In this paper, an acceleration technique based on a Kummer’s transformation method is developed for some slowly convergent series. The original series is decomposed into two parts; one part being rapidly convergent and the other part being slowly convergent. Then the series in the slowly convergent part is expressed as integrals of some auxiliary functions and subsequently they are written in terms of polynomials whose coefficients are given by the zeta functions. The given method is computationally oriented and does not involve much analytic effort. A numerical example is provided to illustrate the usage and the efficiency of the method.     

A comparison of some methods for bounding connected and disconnected solution sets of interval linear systems

Summary Finding bounding sets to solutions to systems of algebraic equations with uncertainties in the coefficients, as well as rapidly but rigorously locating all solutions to nonlinear systems or global optimization problems, involves bounding the solution sets to systems of equations with wide interval coefficients. In many cases, singular systems are admitted within the intervals of uncertainty of the coefficients, leading to unbounded solution sets with more than one disconnected component. This, combined with the fact that computing exact bounds on the solution set is NP-hard, limits the range of techniques available for bounding the solution sets for such systems. However, the componentwise nature and other properties make the interval Gauss–Seidel method suited to computing meaningful bounds in a predictable amount of computing time. For this reason, we focus on the interval Gauss–Seidel method. In particular, we study and compare various preconditioning techniques we have developed over the years but not fully investigated, comparing the results. Based on a study of the preconditioners in detail on some simple, specially–designed small systems, we propose two heuristic algorithms, then study the behavior of the preconditioners on some larger, randomly generated systems, as well as a small selection of systems from the Matrix Market collection.      

General linear methods for ordinary differential equations

General linear methods were introduced as the natural generalizations of the classical Runge–Kutta and linear multistep methods. They have potential applications, especially for stiff problems. This paper discusses stiffness and emphasises the need for efficient implicit methods for the solution of stiff problems. In this context, a survey of general linear methods is presented, including recent results on methods with the inherent RK stability property.     

A minimal residual class of algorithms for linear systems

A family of rapidly convergent algorithms to solve linear systems of equations are described. These methods are easy to implement. In an empirical comparison over a class of problems the presented algorithms were superior to several commonly used methods.     

Using Strassen's algorithm to accelerate the solution of linear systems

Strassen's algorithm for fast matrix-matrix multiplication has been implemented for matrices of arbitrary shapes on the CRAY-2 and CRAY Y-MP supercomputers. Several techniques have been used to reduce the scratch space requirement for this algorithm while simultaneously preserving a high level of performance. When the resulting Strassen-based matrix multiply routine is combined with some routines from the new LAPACK library, LU decomposition can be performed with rates significantly higher than those achieved by conventional means. We succeeded in factoring a 2048 × 2048 matrix on the CRAY Y-MP at a rate equivalent to 325 MFLOPS.This work is supported through NASA Contract NAS 2-12961.     

Reduction of Smith Normal Form Transformation Matrices

Smith normal form computations are important in group theory, module theory and number theory. We consider the transformation matrices for the Smith normal form over the integers and give a presentation of arbitrary transformation matrices for this normal form. Our main contribution is an algorithm that replaces already computed transformation matrices by others with small entries. We combine methods from lattice basis reduction with a procedure to reduce the sum of the squared entries of both transformation matrices. This algorithm performs well even for matrices of large dimensions.     

Parallel integration of ODEs based on convolution algorithms

We consider parallel computing methods for ODEs based on the potential parallelism of convolution algorithms. Detailed presentations of fast convolution algorithms are provided. Implementations of our methods on signal processors and special processors are described. The main emphasis is concentrated on applications of powerful parallel signal processing facilities in ODE computations. By using convolution algorithms we show some treatments of parallel computing in finite fields. As an example of our approach we discuss integrating Lorenz's model.

---

Zusammenfassung Wir behandeln parallele numerische Methoden für gewöhnliche Differentiagleichungen, die auf Parallelismus von konvolutiven Algorithmen basieren. Ausführliche Darstellungen der schnellen konvolutiven Berechnungen mit spezieller Hardware werden präsentiert. Der Schwerpunkt dieser Arbeit ist die Anwendung von leistungsfähigen parallelen Signal-Prozessoren in der Berechnung gewöhnlicher Differentialgleichungen. Unter Verwendung von Konvolutiven Algorithmen erläutern wir einige Anwendungen von parallelem Rechnen in endlichen Körpern. Als Beispiel unseres Zugangs diskutieren wir die Integration des Lorenz-Modells.

     

Incomplete Cross Approximation in the Mosaic-Skeleton Method

The mosaic-skeleton method was bred in a simple observation that rather large blocks in very large matrices coming from integral formulations can be approximated accurately by a sum of just few rank-one matrices (skeletons). These blocks might correspond to a region where the kernel is smooth enough, and anyway it can be a region where the kernel is approximated by a short sum of separable functions (functional skeletons). Since the effect of approximations is like that of having small-rank matrices, we find it pertinent to say about mosaic ranks of a matrix which turn out to be pretty small for many nonsingular matrices. On the first stage, the method builds up an appropriate mosaic partitioning using the concept of a tree of clusters and some extra information rather than the matrix entries (related to the mesh). On the second stage, it approximates every allowed block by skeletons using the entries of some rather small cross which is chosen by an adaptive procedure. We focus chiefly on some aspects of practical implementation and numerical examples on which the approximation time was found to grow almost linearly in the matrix size. Received February 13, 1999; revised October 26, 1999     

Construction and Arithmetics of <Emphasis Type="Italic">H</Emphasis>-Matrices

In previous papers hierarchical matrices were introduced which are data-sparse and allow an approximate matrix arithmetic of nearly optimal complexity. In this paper we analyse the complexity (storage, addition, multiplication and inversion) of the hierarchical matrix arithmetics. Two criteria, the sparsity and idempotency, are sufficient to give the desired bounds. For standard finite element and boundary element applications we present a construction of the hierarchical matrix format for which we can give explicit bounds for the sparsity and idempotency.     

On the solution of a quasi-tridiagonal system of linear equations

A method is described for solving a system of linear algebraic equations which is almost tridiagonal. Numerical results are presented for a number of test problems and some comparisons are made with the results obtained from algorithms proposed by other authors. A possible extension of the technique is briefly outlined.     

Order conditions for ARKN methods solving oscillatory systems

For the perturbed oscillators in one-dimensional case, J.M. Franco designed the so-called Adapted Runge-Kutta-Nyström (ARKN) methods and derived the sufficient order conditions as well as the necessary and sufficient order conditions for ARKN methods based on the B-series theory [J.M. Franco, Runge-Kutta-Nyström methods adapted to the numerical integration of perturbed oscillators, Comput. Phys. Comm. 147 (2002) 770-787]. These methods integrate exactly the unperturbed oscillators and are highly efficient when the perturbing function is small. Unfortunately, some critical mistakes have been made in the derivation of order conditions in that paper. On the basis of the results from that paper, Franco extended directly the ARKN methods and the corresponding order conditions to multidimensional case where the perturbed function f does not depend on the first derivative y^′ [J.M. Franco, New methods for oscillatory systems based on ARKN methods, Appl. Numer. Math. 56 (2006) 1040-1053]. In this paper, we present the order conditions for the ARKN methods for the general multidimensional perturbed oscillators where the perturbed function f may depend on only y or on both y and y^′.     

Partitioned half-explicit Runge-Kutta methods for differential-algebraic systems of index 2

A class of half-explicit methods for index 2 differential-algebraic systems in Hessenberg form is proposed, which takes advantage of the partitioned structure of such problems. For this family of methods, which we call partitioned half-explicit Runge-Kutta methods, a better choice in the parameters of the method than for previously available half-explicit Runge-Kutta methods can be made. In particular we construct a family of 6-stage methods of order 5, and determine its parameters (based on the coefficients of the successful explicit Runge-Kutta method DOPRI5) in order to optimize the local error coefficients. Numerical experiments demonstrate the efficiency of this method for the solution of constrained multi-body systems.     

Pseudospectra of linear matrix pencils by block diagonalization

We propose an algorithm that block-diagonalizes regular matrix pencils using well conditioned transformations. This algorithm is used for approximating the pseudospectra of matrix pencils. Several numerical experiments illustrate the behavior of the proposed algorithm.     

Errors of linear multistep methods for singularly perturbed Volterra delay-integro-differential equations

This paper is concerned with the error behaviour of linear multistep methods applied to singularly perturbed Volterra delay-integro-differential equations. We derive global error estimates of A(α)$A(\alpha )$-stable linear multistep methods with convergent quadrature rule. Numerical experiments confirm our theoretical analysis.