Two algorithms for treating ax = λbx

The first algorithm is a generalization of the iterative method of successive coordinate overrelaxation. Instead of computing a single eigenvalue and its corresponding eigenvector at a time, p vectors are iterated simultaneously in such a way that they converge ultimately towards the eigenvectors corresponding to the p smallest eigenvalues. This method of simultaneous group coordinate overrelaxation has the advantage of taking into account the sparseness of the matrices A and B to full extent, to operate on the originally given matrices and to require a relatively small working storage space.The second algorithm is a variant of the well-known bisection method. It is shown that the inertia theorem for quadratic forms can be applied to localize the eigenvalues. Hence, an appropriate congruence transformation of the matrix A ? βB, which is assumed now to be banded, allows one to determine the number of eigenvalues that are smaller than μ. In order to increase the numerical stability of the reduction process, a partial pivoting is applied consisting of auxiliary congruence transformations in such a way that the band width is only doubled. This approach to the bisection method is conceptually much simpler - the actual algorithm preserves the symmetry and requires a smaller working storage space for the computation of the eigenvectors by inverse vector iteration in comparison with the well-known realizations of the bisection method.     

Zur Bestimmung der Frobeniuswurzel nichtnegativer Matrizen

We give an iterative method for determining nested bounds for the Frobenius-rootr(A) of a nonnegative matrixA. This method still works when there are several eigenvalues with modulusr(A).     

A global jacobi method for a symmetric indefinite problem Sx = λTx

A reliable Jacobi-like method for the problem Sx = λTx has been presented where S and T are real, symmetric but indefinite, and T has the same number of positive and negative eigenvalues as it occurs in standard problems of damped oscillations of structures. The method is quadratically convergent in all non-defective cases including also the cases of double defective real eigenvalues which correspond to the physically important phenomenon of critical damping. The symmetry is preserved in all stages which carries a 50% saving of both computing time and space. The experimental comparison with the QR method and the standard complex method of Eberlein has been made. The present method has shown to be particularly suitable for diagonally dominant matrices as they appear e.g. in subspace iterations.     

A fully parallel method for the singular eigenvalue problem

In this paper, a fully parallel method for finding some or all finite eigenvalues of a real symmetric matrix pencil (A, B) is presented, where A is a symmetric tridiagonal matrix and B is a diagonal matrix with b₁ > 0 and b_i ≥ 0, i = 2,3,…,n. The method is based on the homotopy continuation with rank 2 perturbation. It is shown that there are exactly m disjoint, smooth homotopy paths connecting the trivial eigenvalues to the desired eigenvalues, where m is the number of finite eigenvalues of (A, B). It is also shown that the homotopy curves are monotonic and easy to follow.     

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 systems of linear equations of the form AtAx = b error analysis and certain consequences for structural applications

An error analysis of the solution of linear systems of the form $\text{A}{}^{\mathrm{t}}\text{Ax = b}$ is presented. The analysis is based on the backward technique of J.H. Wilkinson applied to the QR method on A, which involves the use of elementary Hermitians. The accuracy of the method is compared to that of the classical Cholesky approach on the formed product $\text{K = A}{}^{\mathrm{t}}\text{A}$. Although the initial analysis shows no improved error bound for the QR approach compared to the Cholesky method, a more refined treatment reveals that the relative solution error using QR methods is usually considerably smaller than that using the Cholesky procedure, particularly for commonly occurring right-hand side vectors b.Practical error estimates are provided, both based on the spectral conditioning number measure as well as on the first correction in a special iterative improvement technique.As systems of equations similar to the above arise in the new natural factor technique of J.H. Argyris and O.E. Brönlund for matrix structural analysis, some discussion of structural applications in both statics and dynamics is presented. It is shown that the only case where the accuracy of the QR method is not considerably better than that for Cholesky reduction corresponds to an unusual physical situation. In addition, a natural factor formulation for the mixed method in finite element analysis is presented, extending the first writer's previous work on this topic.Finally, several numerical examples are given, based on randomly generated data as well as on data from real structures, to demonstrate the validity and applicability of the method and the corresponding error analysis.     

On the connection between the exponential stability of C0-semigroups and the admissibility of a certain Sobolev space

Let T be a strongly continuous semigroup on a Banach space X and A its infinitesimal generator. We will prove that T is exponentially stable, if and only if, there exist p[1,∞) such that the space is admissible to the system Σ(A,I,I), defined below (i.e for all f belonging to the Sobolev space the convolution T*f lies in .     

Joint affinity aware grouping and virtual machine placement

The Non-Affinity Aware Grouping based resource Allocation (NAGA) method toward the General VMPlacement (GP) problem enables (1) some VMs to be co-located onto the same PM while the VMs are required to be placed onto distinct PMs; and (2) some VMs to be dispersedly placed onto distinct PMs while the VMs are required to be co-located onto the same PM, leading to a serious performance degradation of application running over multiple VMs in cloud computing. In this work we study an Affinity Aware VM Placement (AAP) problem and propose a Joint Affinity AwareGrouping and Bin Packing (JAGBP) method to remedy the deficiency of the NAGA method. We firstly introduce affinity of VMs to identify affinity relationships to VMs which are required to be placed with a special VM placement pattern, such as colocation or disperse placement, and formulate the AAP problem. Then, we propose an affinity aware resource scheduling framework, and provide methods to obtain and identify the affinity relationships between VMs, and the JAGBP method. Lastly, we present holistic evaluation experiments to validate the feasibility and evaluate the performance of the proposed methods. The results demonstrate the significance of introduced affinity and the effectiveness of JAGBP method.     

LU-decomposition and numerical structure for solving large sparse nonsymmetric linear systems

In this work, the solution of a large sparse linear system of equations with an arbitrary sparsity pattern is obtained by using LU-decomposition method as well as numerical structure approach. The LU-decomposition method is based on Doolittle's method while the numerical structure approach is based on Cramer's rule. The numerical structure approach produces direct solution without facing fill-in problems as encountered in LU-decomposition. In order to reduce the ‘fill-ins’ in the decomposition, the powers of a Boolean matrix, obtained from the coefficient matrix A are taken so that the ‘fill-ins’ in the structure of A can be known in advance. The position of fill-ins in A are thus determined in the best choice manner, that is, it is very effective and memory-wise cheap. We also outline a method by using numerical structure with reduced computation efforts.Finally, experiments are performed on eight examples to compare the efficiency of the proposed methods. The results obtained are reported in a table. It is found that the LU-decomposition method is much better than numerical structure. The usefulness of numerical structure approach is also discussed.     

Bisection forAx=λBx with matrices of variable band width

Some extensions of the bisection method and of the inverse vector iteration for the general eigenvalue problemAx=λBx with symmetric matrices are given. A version with restricted pivoting is applied to sparse matricesA andB in which case the decomposition ofA-μB can be performed within an extended envelope with respect to the envelopeA andB. The effect of these refinements is illustrated by an example.     

Numerical solution of AS + SA + Q = 0

A survey of techniques to solve A^TS + SA + Q = 0 is presented, and nine algorithms are coded and tested on a batch of examples. Which algorithm to be recommended depends mainly on the order of the system.     

Supporting early pruning in top-k query processing on massive data

This paper analyzes the execution behavior of “No Random Accesses” (NRA) and determines the depths to which each sorted file is scanned in growing phase and shrinking phase of NRA respectively. The analysis shows that NRA needs to maintain a large quantity of candidate tuples in growing phase on massive data. Based on the analysis, this paper proposes a novel top-k algorithm Top-K with Early Pruning (TKEP) which performs early pruning in growing phase. General rule and mathematical analysis for early pruning are presented in this paper. The theoretical analysis shows that early pruning can prune most of the candidate tuples. Although TKEP is an approximate method to obtain the top-k result, the probability for correctness is extremely high. Extensive experiments show that TKEP has a significant advantage over NRA.     

Measuring the understanding between two agents through concept similarity

Two agents previously unknown to each other cannot communicate by exchanging concepts (nodes of their own ontology): they need to use a common communication language. If they do not use a standard protocol, most likely they use a natural language. The ambiguities of it, and the different concepts the agents possess, give rise to imperfect understanding among them: How closely concepts in ontology O_A map¹ to which of O_B? Can we measure these mismatches?Given a concept from ontology O_A, a method is provided to find the most similar concept in O_B, and to measure the similarity between both concepts. The paper also gives an algorithm to gauge du(A, B), the degree of understanding that agent A has about the ontology of B. The procedures use word comparison, since no agent (except the Very Wise Creature, VWC) can measure du directly. Examples are given.     

An iterative method for solving partitioned linear equations

A new iterative scheme, using two partitions of the coefficient matrix of a given linear and non-singular system of equationsAx=b, is shown to always converge to the solution. The concept of two vector spaces approaching orthogonality is quantified and used to show that the eigenvalues of the iteration matrix approach zero as the vector spaces defined by the two partitions ofA approach orthogonality.     

Computing eigenvalue bounds for iterative subspace matrix methods

A procedure is presented for the computation of bounds to eigenvalues of the generalized hermitian eigenvalue problem and to the standard hermitian eigenvalue problem. This procedure is applicable to iterative subspace eigenvalue methods and to both outer and inner eigenvalues. The Ritz values and their corresponding residual norms, all of which are computable quantities, are needed by the procedure. Knowledge of the exact eigenvalues is not needed by the procedure, but it must be known that the computed Ritz values are isolated from exact eigenvalues outside of the Ritz spectrum and that there are no skipped eigenvalues within the Ritz spectrum range. A multipass refinement procedure is described to compute the bounds for each Ritz value. This procedure requires O(m) effort where m is the subspace dimension for each pass.     

Monte Carlo TD(λ)-methods for the optimal control of discrete-time Markovian jump linear systems

In this paper, we present an iterative technique based on Monte Carlo simulations for deriving the optimal control of the infinite horizon linear regulator problem of discrete-time Markovian jump linear systems for the case in which the transition probability matrix of the Markov chain is not known. We trace a parallel with the theory of TD(λ) algorithms for Markovian decision processes to develop a TD(λ) like algorithm for the optimal control associated to the maximal solution of a set of coupled algebraic Riccati equations (CARE). It is assumed that either there is a sample of past observations of the Markov chain that can be used for the iterative algorithm, or it can be generated through a computer program. Our proofs rely on the spectral radius of the closed loop operators associated to the mean square stability of the system being less than 1.     

Bounds for sums of eigenvalues and applications

Let A be a matrix of order n × n with real spectrum λ₁ ≥ λ₂ ≥ ⋯ ≥ λ_n. Let 1 ≤ k ≤ n − 2. If λ_n or λ₁ is known, then we find an upper bound (respectively, lower bound) for the sum of the k-largest (respectively, k-smallest) remaining eigenvalues of A. Then, we obtain a majorization vector for (λ₁, λ₂,…, λ_n−1) when λ_n is known and a majorization vector for (λ₂, λ₃,…, λ_n) when λ₁ is known. We apply these results to the eigenvalues of the Laplacian matrix of a graph and, in particular, a sufficient condition for a graph to be connected is given. Also, we derive an upper bound for the coefficient of ergodicity of a nonnegative matrix with real spectrum.     

On the numerical solution of the eigenvalue problem of the laplace operator by a capacitance matrix method

The problem of finding several eigenfunctions and eigenvalues of the interior Dirichlet problem for Laplace's equation on arbitrary bounded plane regions is considered. Two fast algorithms are combined: an iterative Block Lanczos method and a capacitance matrix method. The capacitance matrix is generated and factored only once for a given problem. In each iteration of the Block Lanczos method, a discrete Helmholtz equation is solved twice on a rectangle at a cost of the order ofn ² log₂ n operations wheren is the number of mesh points across the rectangle in which the region is imbedded.     

Undecidability of the first-order arithmetic A[P(x), 2x, x + 1]

It is shown that the first-order arithmetic A[P(x), 2x, x + 1] with two functions 2x, x + 1 and a monadic predicate symbol P(x) is undecidable, by using a kind of two-dimensional finite automata, called finite causal ω²-systems. From this immediately follows R.M. Robinson's result, which says that the monadic second-order theory with two functions 2x, x + 1 is undecidable. This is also considered as an improvement on H. Putnam's result about the undecidability of the first-order arithmetic with addition and a monadic predicate symbol.     

Trigonometric transform splitting methods for real symmetric Toeplitz systems

In this paper we study efficient iterative methods for real symmetric Toeplitz systems based on the trigonometric transformation splitting (TTS) of the real symmetric Toeplitz matrix $A$. Theoretical analyses show that if the generating function $f$ of the $n\times n$ Toeplitz matrix $A$ is a real positive even function, then the TTS iterative methods converge to the unique solution of the linear system of equations for sufficient large $n$. Moreover, we derive an upper bound of the contraction factor of the TTS iteration which is dependent solely on the spectra of the two TTS matrices involved.Different from the CSCS iterative method in Ng (2003) in which all operations counts concern complex operations when the DFTs are employed, even if the Toeplitz matrix $A$ is real and symmetric, our method only involves real arithmetics when the DCTs and DSTs are used. The numerical experiments show that our method works better than CSCS iterative method and much better than the positive definite and skew-symmetric splitting (PSS) iterative method in Bai et al. (2005) and the symmetric Gauss–Seidel (SGS) iterative method.