The group-coordinate relaxation method for solving the generalized eigenvalue problem for large real-symmetric matrices

A method is described for solving the generalized eigenvalue problem for very large matrices which are not sparse and in which the off-diagonal elements are not small compared with the diagonal ones. This method has been found to succeed where others have failed.     

Parallel implementations of the trace minimization scheme TraceMIN for the sparse symmetric eigenvalue problem

Eigenvalue problems arise in many computational science and engineering applications: in structural mechanics, nanoelectronics, and Google’s PageRank link analysis, for example. Often, the large size of these eigenvalue problems requires the development of eigensolvers that scale well on parallel computing platforms. In this paper, we compare the effectiveness and robustness of our eigensolver for the symmetric generalized eigenvalue problem, the trace minimization scheme TraceMIN–developed in the early 1980s–against today’s well-known sparse eigensolvers including: the LOBPCG and block Krylov–Schur implementations in Trilinos; ARPACK; and several methods in the PRIMME package such as the Jacobi–Davidson one. In addition, we demonstrate the parallel scalability of two variants of TraceMIN on multicore nodes as well as on large clusters of such nodes. Our results show that TraceMIN is more robust and has higher parallel scalability than the above-mentioned competing eigensolvers.     

An accelerated cyclic-reduction-based solvent method for solving quadratic eigenvalue problem of gyroscopic systems

The quadratic eigenvalue problem (QEP) $({\lambda }^{2}M+\lambda G+K)x=0$, with $M^T=M$ being positive definite, $K^T=K$ being negative definite and $G^T=?G$, is associated with gyroscopic systems. In Guo (2004), a cyclic-reduction-based solvent (CRS) method was proposed to compute all eigenvalues of the above mentioned QEP. Firstly, the problem is converted to find a suitable solvent of the quadratic matrix equation (QME) $M{X}^2+GX+K=0$. Then using a Cayley transformation and a proper substitution, the QME is transformed into the nonlinear matrix equation (NME) $Z+A^T{Z}^{?1}A=Q$ with $A=M+K+G$ and $Q=2(M?K)$. The problem finally can be solved by applying the CR method to obtain the maximal symmetric positive definite solution of the NME as long as the QEP has no eigenvalues on the imaginary axis or for some cases where the QEP has eigenvalues on the imaginary axis. However, when all eigenvalues of the QEP are far away from or near the origin, the Cayley transformation seems not to be the best one and the convergence rate of the CRS method proposed in Guo (2004) might be further improved. In this paper, inspired by using a doubling algorithm to solve the QME, we use a Möbius transformation instead of the Cayley transformation to present an accelerated CRS (ACRS) method for solving the QEP of gyroscopic systems. In addition, we discuss the selection strategies of optimal parameter for the ACRS method. Numerical results demonstrate the efficiency of our method.     

Refinements on an enumeration scheme for solving a pattern sequencing problem

We introduce some refinements on a branch‐ and bound‐scheme for solving the minimization of open stack problem (MOSP). After representing the MOSP as a graph traversing problem, we attempt to divide the graph into parts aiming to solve the resulting subgraphs independently in order to reduce the search in the branching scheme. Subgraphs with special topologies (such as trees) are solved exactly using polynomial time algorithms. The branching scheme is applied only to the parts that are ‘complex’. The refinements introduced produce substantial savings in computational time when the MOSP graph presents some special structures. Limited computational results are presented.     

Efficient difference scheme for numerical solution of a convective diffusion problem

Problems of modeling of atmospheric circulation are investigated. A new method for solution of a one-dimensional nonstationary inhomogeneous initial-boundary-value problem of convective diffusion is considered. The problem is solved using a new unconditionally stable and efficient difference scheme. The results of a theoretical analysis of the scheme are presented. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 64–74, May–June 2007. An erratum to this article is available at .     

A new fourth-order difference scheme for solving an N-carrier system with Neumann boundary conditions

In this paper, a numerical method is developed to solve an N-carrier system with Neumann boundary conditions. First, we apply the compact finite difference scheme of fourth order for discretizing spatial derivatives at the interior points. Then, we develop a new combined compact finite difference scheme for the boundary, which also has fourth-order accuracy. Lastly, by using a Padé approximation method for the resulting linear system of ordinary differential equations, a new compact finite difference scheme is obtained. The present scheme has second-order accuracy in time direction and fourth-order accuracy in space direction. It is shown that the scheme is unconditionally stable. The present scheme is tested by two numerical examples, which show that the convergence rate with respect to the spatial variable from the new scheme is higher and the solution is much more accurate when compared with those obtained by using other previous methods.     

Fast relaxation method for solving the difference problem for the poisson equation on a sequence of grids

A method for accelarating the convergence of iterative processes on a sequence of grids is proposed, which makes use of the decomposition of the difference solution into powers of the discretization step. Approximation solutions from a number of auxiliary grids are extrapolated to the exact solution on the finest grid. In the case of a difference problem for the Poisson equation the error of such extrapolation on the last grid is quickly suppressed by simple iterations due to some smoothness properties of the difference-operator eigenfunctions. The results of numerical experiments are presented which illustrate the high efficiency of the proposed method for solution of the given problem.     

Finite difference methods for solving

In this report, finite difference methods of orders 2 and 4 are developed and analysed for the solution of a two-point boundary value problem associated with a fourth- order linear differential equation. A sufficient condition guaranteeing a unique solution of the boundary value problem is also given. Numerical results for a typical boundary value problem are tabulated and compared with the shooting technique using the fourth-order Runge-Kutta method.     

A self-adaptive memeplexes robust search scheme for solving stochastic demands vehicle routing problem

In this article, we proposed a self-adaptive memeplex robust search (SAMRS) for finding robust and reliable solutions that are less sensitive to stochastic behaviours of customer demands and have low probability of route failures, respectively, in vehicle routing problem with stochastic demands (VRPSD). In particular, the contribution of this article is three-fold. First, the proposed SAMRS employs the robust solution search scheme (RS ³) as an approximation of the computationally intensive Monte Carlo simulation, thus reducing the computation cost of fitness evaluation in VRPSD, while directing the search towards robust and reliable solutions. Furthermore, a self-adaptive individual learning based on the conceptual modelling of memeplex is introduced in the SAMRS. Finally, SAMRS incorporates a gene-meme co-evolution model with genetic and memetic representation to effectively manage the search for solutions in VRPSD. Extensive experimental results are then presented for benchmark problems to demonstrate that the proposed SAMRS serves as an efficable means of generating high-quality robust and reliable solutions in VRPSD.     

Mean Laplacian mappings-based difference LDA for face recognition

Multimedia Tools and Applications - This paper proposes a difference LDA based on mean Laplacian mappings. For each pixel, we firstly estimate multiple mean Laplacian mappings which include an odd...     

The eigenvalue problem for banded matrices

The generalized Lanczos method is used for the purpose of calculating frequencies and mode shapes for linearly elastic discretized structures where the energy-consistent stiffness and mass matrices are equally banded. This approach involves reduction of the problem to standard tridiagonal form without expanding the band width of either of the original arrays. Applications of the method to both vibrational and buckling analyses indicate its potential for conserving core storage when solving the eigenvalue problem on a digital computer.     

On maximizing the second smallest eigenvalue of a state-dependent graph Laplacian

We consider the set G consisting of graphs of fixed order and weighted edges. The vertex set of graphs in G will correspond to point masses and the weight for an edge between two vertices is a functional of the distance between them. We pose the problem of finding the best vertex positional configuration in the presence of an additional proximity constraint, in the sense that, the second smallest eigenvalue of the corresponding graph Laplacian is maximized. In many recent applications of algebraic graph theory in systems and control, the second smallest eigenvalue of Laplacian has emerged as a critical parameter that influences the stability and robustness properties of dynamic systems that operate over an information network. Our motivation in the present work is to "assign" this Laplacian eigenvalue when relative positions of various elements dictate the interconnection of the underlying weighted graph. In this venue, one would then be able to "synthesize" information graphs that have desirable system theoretic properties.     

An algorithm for the multiinput eigenvalue assignment problem

A very simple and inexpensive algorithm is presented for pole placement in the multiinput case. The algorithm consists of orthogonal reduction to a Block-Hessenberg form and a simple linear recursion. It yields a matrix F such that A+BF has any specified set of eigenvalues whenever the system is controllable. It is extremely easy to program on a computer. The algorithm is not a robust pole-placement algorithm but appears to give comparable results in most well-conditioned cases at a fraction of the cost. It is a direct (noniterative) algorithm and no eigenvalues or singular values are computed. The algorithm does not need any complex arithmetic, even when complex conjugate eigenvalues need to be assigned     

Uniformly convergent second-order difference scheme for a singularly perturbed periodical boundary value problem

A periodic boundary value problem with a small parameter multiplying the first- and second-order derivatives is considered. The problem is discretized using a hybrid difference scheme on a Shishkin mesh. We show that the scheme is almost second-order convergent in the maximum norm, which is independent of a singular perturbation parameter. Numerical experiment supports these theoretical results.     

A stable time advancing scheme for solving fluid-structure interaction problem at small structural displacements

A semi-implicit time advancing scheme for transient fluid-structure interaction problem is presented. At every time step, a least squares problem is solved by partitioned procedures, such that the continuity of the velocity as well as the continuity of the stress hold at the interface. During the iterative method for solving the optimization problem, the fluid mesh does not move, which reduces the computational effort. The stability of the algorithm is derived. The numerical results presented in this paper show that the computed solution is similar to the one obtained by the implicit algorithm, but the computational time is reduced.     

A Riccati-type algorithm for solving generalized Hermitian eigenvalue problems

The paper describes a heuristic algorithm for solving a generalized Hermitian eigenvalue problem fast. The algorithm searches a subspace for an approximate solution of the problem. If the approximate solution is unacceptable, the subspace is expanded to a larger one, and then, in the expanded subspace a possibly better approximated solution is computed. The algorithm iterates these two steps alternately. Thus, the speed of the convergence of the algorithm depends on how to generate a subspace. In this paper, we derive a Riccati equation whose solution can correct the approximate solution of a generalized Hermitian eigenvalue problem to the exact one. In other words, the solution of the eigenvalue problem can be found if a subspace is expanded by the solution of the Riccati equation. This is a feature the existing algorithms such as the Krylov subspace algorithm implemented in the MATLAB and the Jacobi–Davidson algorithm do not have. However, similar to solving the eigenvalue problem, solving the Riccati equation is time-consuming. We consider solving the Riccati equation with low accuracy and use its approximate solution to expand a subspace. The implementation of this heuristic algorithm is discussed so that the computational cost of the algorithm can be saved. Some experimental results show that the heuristic algorithm converges within fewer iterations and thus requires lesser computational time comparing with the existing algorithms.

     

On the correction of finite difference eigenvalue approximations for Sturm-Liouville problems

The use of algebraic eigenvalues to approximate the eigenvalues of Sturm-Liouville operators is known to be satisfactory only when approximations to the fundamental and the first few harmonics are required. In this paper, we show how the asymptotic error associated with related but simpler Sturm-Liouville operators can be used to correct certain classes of algebraic eigenvalues to yield uniformly valid approximations.