On the use of parallel processors for implicit Runge-Kutta methods

An iteration scheme, for solving the non-linear equations arising in the implementation of implicit Runge-Kutta methods, is proposed. This scheme is particularly suitable for parallel computation and can be applied to any method which has a coefficient matrixA with all eigenvalues real (and positive). For such methods, the efficiency of a modified Newton scheme may often be improved by the use of a similarity transformation ofA but, even when this is the case, the proposed scheme can have advantages for parallel computation. Numerical results illustrate this. The new scheme converges in a finite number of iterations when applied to linear systems of differential equations, achieving this by using the nilpotency of a strictly lower triangular matrixS ^?1 AS — Λ, with Λ a diagonal matrix. The scheme reduces to the modified Newton scheme whenS ^?1 AS is diagonal.A convergence result is obtained which is applicable to nonlinear stiff systems.     

Eine Anwendung des Brouwerschen Fixpunktsatzes in der Intervallarithmetik der Matrizen

A theorem is proved by means of Brouwer's theorem which allows to decide whether a given interval matrix [S] has the inclusion property relative to the unknown inverseA ^?1 of a known matrixA. It is demonstrated in which cases the theorem may be used and how to choose [S] in these cases.     

A theorem for locating eigenvalues

The primary conclusion derived in this paper is that the leading principal minors of matrixB-ωA (whereB is a symmetric positive definite matrix andA is Hermite matrix) have properties similar to those of Sturm sequences, which is the theoretical basis of the Determinant Search Method for solving the eigenvalue-problem of damped structural systems [1]–[5], correcting the errors in a statement given by K. K. Gupta in [1]–[5].     

A generalization of the Schützenberger product of finite monoids

For each n?1, an n-ary product ? on finite monoids is constructed. This product has the following property: Let Σ be a finite alphabet and Σ¹ the free monoid generated by Σ. For i = 1, …,n, let A_i be a recognizable subset of Σ¹, M(A_i) the syntactic monoid of A_n and M(A₁?A_n) the syntactic monoid of the concatenation product A₁?A_n. Then M(A₁?A_n)< ? (M(A₁),…,M(A_n)). The case n = 2 was studied by Schützenberger. As an application of the generalized product, I prove the theorem of Brzozowski and Knast that the dot-depth hierarchy of star-free sets is infinite.     

Solving linear least squares by orthogonal factorization and pseudoinverse computation via the modified Huang algorithm in the ABS class

We consider three algorithms for solving linear least squares problems based upon the modified Huang algorithm (MHA) in the ABS class for linear systems recently introduced by Abaffy, Broyden and Spedicato. The first algorithm uses an explicit QR factorization of the coefficient matrixA computed by applying MHA to the matrixA ^T . The second and the third algorithm is based upon two representations of the Moore-Penrose pseudoinverse constructed with the use of MHA. The three algorithms are tested on a large set of problems and compared with the NAG code using QR factorization with Householder rotations. The comparison shows that the algorithms based on MHA are generally more accurate.     

On a fourth-order unconditionally stable scheme for damped second-order systems

We consider the damped second-order system $\text{M}\text{u}\text{?}\text{+ C/.u + Ku = F(t)}$ (M, C, K symmetric, positive definite n × n matrices) by conversion to an equivalent first-order system

$\text{I}\text{O}\text{O}\text{M}\text{d}\text{d}\text{t}\text{O}\text{?K}\text{I}\text{?C}\text{u}\text{u}\text{?}\text{+}\text{o}\text{F(t)}$

We demonstrate that an algorithm proposed by Fairweather for the implementation of the (2, 2) Padé approximation of the exponential matrix for approximating the solution of homogeneous first-order systems extends advantageously to this case, yielding an unconditionally stable fourth-order scheme with the feature that the approximating equations decouple. As a result we are required only to solve one symmetric complex n × n system of linear algebraic equations at each time step, with a fixed matrix which may be decomposed into triangular factors at the outset. We also consider iterative schemes involving only real, positive definite, symmetric n × n matrices. Numerical results are included.     

Some investigation on Hermitian positive-definite solutions of a nonlinear matrix equation

In this paper, the Hermitian positive-definite solutions of the matrix equation X^s+A*X^?tA=Q are considered. New necessary and sufficient conditions for the equation to have a Hermitian positive-definite solution are derived. In particular, when A is singular, a new estimate of Hermitian positive-definite solutions is obtained. In the end, based on the fixed point theorem, an iterative algorithm for obtaining the positive-definite solutions of the equation with Q=I is discussed. The error estimations are found.     

Block splittings for the conjugate gradient method

We study the generalized conjugate gradient scheme, based on the k-line and k × k block Jacobi splittings A = M ? N, for solving two-dimensional parabolic and elliptic difference equations $\text{AU =}\text{F}\text{?}$. Here A represents the difference operator ch^α ? h²Δ_h. Computational experiments suggest that the eigenvalues of K: = I ? M^?1N cluster, and that the cluster radii decrease as k or ch^α increases. As is well known, clustering improves convergence of the conjugate gradient iterates. We discuss computational results for k = 4, 8, 16, 32 and for ch^α = 0, h, 2. Moreover, we establish the number and size of eigenvalue clusters for the model problem.     

Nearly tight bounds on the number of Hamiltonian circuits of the hypercube and generalizations

It has been shown that for every perfect matching M of the d-dimensional n-vertex hypercube, d?2, n=d², there exists a second perfect matching M^′ such that the union of M and M^′ forms a Hamiltonian circuit of the d-dimensional hypercube. We prove a generalization of a special case of this result when there are two dimensions that do not get used by M. It is known that the number Md of perfect matchings of the d-dimensional hypercube satisfies and, in particular, (2d/n)^n/2(n/2)!?Md?(d!)^n/(2d). It has also been shown that the number Hd of Hamiltonian circuits of the hypercube satisfies 1?limd→∞(logHd)/(logMd)?2. We finally strengthen this result to a nearly tight bound ((dlog2/(eloglogd))(1−on(1)))?Hd?(d!)^n/(2d)((d−1)!)^n/(2(d−1))/2 proving that limd→∞(logHd)/(logMd)=2. This means that the bound Hd?Md is improved to a nearly tight , so the number of Hamiltonian circuits in the hypercube is nearly quadratic in the number of perfect matchings. The proofs are based on a result for graphs that are the Cartesian product of squares and arbitrary bipartite regular graphs that have a Hamiltonian cycle. We also study a labeling scheme related to matchings.     

Sturm sequences or law of inertia of quadratic forms?

In obtaining the number of eigenvalues greater than a given constant λ₀ of the eigenvalue problem [A]{x} = λ[B]{x} with [A] and [B] real, symmetric, and [B] positive definite, one usually refers to the Sturm sequence established by the leading principal minors of [A–λ₀B], the proof of which is given basically when the associated special eigenvalue problem is tridiagonal. In this work, using the law of inertia of quadratic forms, it is shown that the number of eigenvalues of [A]{x}] = λ[B]{x} greater than a given constant λ₀ (not an eigenvalue) is the number of positive entries of the diagonal matrix [d] in the identity [A–λ₀B] = [u]^T[d][u] where [u] is the upper triangular matrix associated with Crout-Banachievicz type decomposition of [A –λ₀B], without the help of the separation theorem and the Sturm sequence.     

Numerical algorithms for undamped gyroscopic systems

The solutions of a gyroscopic vibrating system oscillating about an equilibrium position, with no external applied forces and no damping forces, are completely determined by the quadratic eigenvalue problem (−λ²_iM + λ_iG + K)x_i = 0, for i = 1, …, 2n, where M, G, and K are real n × n matrices, and M is symmetric positive definite (denoted by M > 0), G is skew symmetric, and either K > 0 or − K > 0. Gyroscopic system in motion about a stable equilibrium position (with − K > 0) are well understood. Two Lanczos-type algorithms, the pseudo skew symmetric Lanczos algorithm and the J-Lanczos algorithm, are studied for computing some extreme eigenpairs for solving gyroscopic systems in motion about an unstable equilibrium position (with K > 0). Shift and invert strategies, error bounds, implementation issues, and numerical results for both algorithms are presented in details.     

A program generator for the incomplete cholesky conjugate gradient (ICCG) method with a symmetrizing preprocessor

This paper is an extension of our previous paper “A program generator for the Incomplete LU-decomposition-Conjugate Gradient (ILUCG) method” which appeared in Computer Physics Communications. In that paper we presented a generator program which produced a code package to solve the system of equations Ax = bb, where A is an arbitrary nonsingular matrix, by the ILUCG method. In the present paper we offer an alternative generator program which produces a code package applicable to the case where A is symmetric and positive definite. The numerical algorithm used is the Incomplete Cholesky Conjugate Gradient (ICCG) method of Meijerink and Van der Vorst which executes approximately twice as fast per iteration as the ILUCG method. In addition, we provide an optional preprocessor to treat the case of a not diagonally dominant nonsymmetric and nonsingular matrix A by solving the equation A^TAx = A^Tb.     

On relativizing auxiliary pushdown machines

We consider relativizing the constructions of Cook in [4] characterizing space-bounded auxiliary pushdown automata in terms of timebounded computers. LetS(n) ≥ logn be a measurable space bound. LetDT ^A[NT^A] be the class of setsS such that there exists a machineM such thatM with oracleA recognizes the setS andM is a deterministic [nondeterministic] oracle Turing machine acceptor that runs in time 2 ^cS(n) for some constantc. LetDB _i ^A [NB _i ^A ] be the class of setsS such that there exists a machineM such thatM with oracleA recognizes the setS andM is a deterministic [non-deterministic] oracle Turing machine acceptor with auxiliary pushdown that runs in spaceS(n) and never queries the oracle about strings longer than:S(n) ifi = 1, 2 ^cS(n) for some constantc, ifi = 2, + ∞ ifi = 3. Then we prove the following results: These contrast with Cook's (unrelativized) result:DT = NB = DB.     

Extended version with the analysis of dynamic system for iterative refinement of solution

The extended version with the analysis of dynamic system for Wilkinson's iteration improvement of solution is presented in this paper. It turns out that the iteration improvement can be viewed as applying explicit Euler method with step size h=1 to a dynamic system which has a unique globally asymptotically stable equilibrium point, that is, the solution x*=A ^?1 b of linear system Ax=b with non-singular matrix A. As a result, an extended iterative improvement process for solving ill-conditioned linear system of algebraic equations with non-singular coefficients matrix is proposed by following the solution curve of a linear system of ordinary differential equations. We prove the unconditional convergence and derive the roundoff results for the extended iterative refinement process. Several numerical experiments are given to show the effectiveness and competition of the extended iteration refinement in comparison with Wilkinson's.     

Note on pencils of matrices

Let A and 8 be hermitian matrices of order n. If X is a real parameter then the adjoint of A + XB can be written as /“~^xA₀+...+ A.A,,_?2 + A_n?it where the A_i are hermitian. It is shown that if A and B are positive-definite (non-negative-definite) then so are the A_i. The ranks of the A_i are also considered. The results of Kocaoglan and Demirekler (1984) are proved in a more concise and clear manner.     

On the RAS-algorithm

Given a nonnegative real (m, n) matrixA and positive vectorsu, v, then the biproportional constrained matrix problem is to find a nonnegative (m, n) matrixB such thatB=diag (x) A diag (y) holds for some vectorsx ∈ ? ^m andy ∈ ? ⁿ and the row (column) sums ofB equalu _i (v _j )i=1,...,m(j=1,..., n). A solution procedure (called the RAS-method) was proposed by Bacharach [1] to solve this problem. The main disadvantage of this algorithm is, that round-off errors slow down the convergence. Here we present a modified RAS-method which together with several other improvements overcomes this disadvantage.     

Ein Iterationsverfahren,welches die optimale Intervall-Einschließung des Inversen eines M-Matrixintervalls liefert

Let beX the set of all inverse matricesA ^?1, whereA is contained in a given M-matrixinterval. Then using some properties of M-matrices it will be proved, that an interval version of the Schulz-method produces universally — i. e. without any restrictive condition for convergence — the best possible interval inclusion of the setX.     

A new matrix test for randomness

Let ${{\mathcal S}}$ be one of the two multiplicative semigroups: M × M Boolean matrices, or the semigroup of M × M matrices over the field GF(2). Then for any matrix ${A\in {\mathcal S}}$ there exist two unique smallest numbers, namely the index and period k, d, such that A ^k  = A ^k+d . This fact allows us to form a new statistical test for randomness which we call the Semigroup Matrix Test. In this paper, we present details and results of our experiments for this test. We use Boolean matrices for M = 2, . . . , 5, and matrices over GF(2) of the size M = 2, . . . , 6. We also compare the results with the results obtained by the well-known Binary Matrix Rank Test.     

Two-Grid Discontinuous Galerkin Method for Quasi-Linear Elliptic Problems

In this paper, we consider the symmetric interior penalty discontinuous Galerkin (SIPG) method with piecewise polynomials of degree r≥1 for a class of quasi-linear elliptic problems in Ω⊂ℝ². We propose a two-grid approximation for the SIPG method which can be thought of as a type of linearization of the nonlinear system using a solution from a coarse finite element space. With this technique, solving a quasi-linear elliptic problem on the fine finite element space is reduced into solving a linear problem on the fine finite element space and solving the quasi-linear elliptic problem on a coarse space. Convergence estimates in a broken H ¹-norm are derived to justify the efficiency of the proposed two-grid algorithm. Numerical experiments are provided to confirm our theoretical findings. As a byproduct of the technique used in the analysis, we derive the optimal pointwise error estimates of the SIPG method for the quasi-linear elliptic problems in ℝ ^d ,d=2,3 and use it to establish the convergence of the two-grid method for problems in Ω⊂ℝ³.     

On the computational complexity of the solution of linear systems with moduli

A problem of solvability for the system of equations of the formAx=D|x|+δ is investigated. This problem is proved to beNP-complete even in the case when the number of equations is equal to the number of variables, the matrixA is nonsingular,A≥D≥0,δ≥0, and it is initially known that the system has a finite (possibly zero) number of solutions. For an arbitrary system ofm equations ofn variables, under additional conditions that the matrixD is nonnegative and its rank is one, a polynomial-time algorithm (of the orderO((max{m, n})³)) has been found which allows to determine whether the system is solvable or not and to find one of such solutions in the case of solvability.