Inverse Toeplitz eigenproblem on personal computer networks

In this paper we present a parallel algorithm for solving the inverse Toeplitz Eigenvalue Problem. The algorithm has been implemented by using a cluster of personal computers, interconnected by a high‐performance Myrinet network. We have utilized standard public domain parallel environments for implementing the calculation part as well as the communications, thus producing portable software. The results obtained allow us to confirm the scalability and efficiency of the algorithm. Moreover, we have checked that by using the theoretical cost model provided by the ScaLAPACK we can predict the behaviour of the experimental results. Copyright © 2000 John Wiley & Sons, Ltd.     

Fast parallel polynomial division via reduction to triangular toeplitz matrix inversion and to polynomial inversion modulo a power

It is known that division with a remainder of two polynomials of degree at most s can be performed over an arbitrary field F of constants using uniform arithmetic and Boolean circuits of depth O(log s log log s) and polynomial size. A new algorithm is presented that yields those bounds via reduction to triangular Toeplitz matrix inversion and to polynomial inversion modulo a power. (If|F| > (s?1)² or if P-uniform computation is allowed, then the depth can be reduced to O(log s).) This approach is new and makes the result conceptually simpler.     

Solving the block–Toeplitz least‐squares problem in parallel

In this paper we present two versions of a parallel algorithm to solve the block–Toeplitz least‐squares problem on distributed‐memory architectures. We derive a parallel algorithm based on the seminormal equations arising from the triangular decomposition of the product T^TT. Our parallel algorithm exploits the displacement structure of the Toeplitz‐like matrices using the Generalized Schur Algorithm to obtain the solution in O(mn) flops instead of O(mn²) flops of the algorithms for non‐structured matrices. The strong regularity of the previous product of matrices and an appropriate computation of the hyperbolic rotations improve the stability of the algorithms. We have reduced the communication cost of previous versions, and have also reduced the memory access cost by appropriately arranging the elements of the matrices. Furthermore, the second version of the algorithm has a very low spatial cost, because it does not store the triangular factor of the decomposition. The experimental results show a good scalability of the parallel algorithm on two different clusters of personal computers. Copyright © 2005 John Wiley & Sons, Ltd.     

New approaches to deriving parallel algorithms

A method is proposed for converting an algorithm admitting no parallel treatment into a new algorithm, in essence, with much better parallel properties. The method is intended for tackling the so called T-algorithms, the term ensuing from first examples of such algorithms concerned in the context of Toeplitz-like matrices. Generalized T-algorithms are also considered.     

Least-squares solutions of constrained inverse eigenproblem and associated optimal approximation problem

In this paper, the least-squares solutions of constrained inverse eigenvalue problem and the associated optimal approximation problem are considered. We get the general expression of the least-squares solutions of the constrained inverse eigenvalue problem, obtain the representation of the unique optimal approximation solution in the least-squares solutions set, and give the algorithm and corresponding computational examples.     

A Parallel Solver for Circulant Toeplitz Tridiagonal Systems on Hypercubes

Solving circulant Toeplitz tridiagonal systems arises in many engineering applications. This paper presents a fast parallel algorithm for solving this type of systems. The number of floating-point operations required in our algorithm is less than the previous parallel algorithm [cf. Kim and Lee (1990)] for solving the similar system. Specifically, an overlapping technique is proposed to reduce the communication steps required. In addition, an error analysis is given. The implementation of our algorithm on the nCUBE2/E with 16 processors has been carried out. The experimental results show that the speedup is almost linearly proportional to the number of processors.     

A split-correct parallel algorithm for solving tridiagonal symmetric toeplitz systems

In 1994, Yan and Chung produced a fast algorithm for solving a diagonally dominant symmetric Toeplitz tridiagonal system of linear equations Ax = b. In this work a method will be presented which will allow for problems of the above nature to be split into two separate systems which can be solved in parallel, and then combined and corrected to obtain a solution to the original system. An error analysis will be provided along with example cases and time comparison results.     

A parallel algorithm solving a tridiagonal Toeplitz linear system

A new tridiagonal Toeplitz linear system (TTLS) solver is proposed. The solver first decomposes an n-dimensional strictly diagonally dominant TTLS equation into a number of m-dimensional subsystems employing a modified Gaussian elimination method. An analytic solution of a continued fraction is obtained to derive the solver. The solver based on the modified Gaussian elimination method fully exploits parallelism. Computation and communication complexities of the proposed algorithm are all shown to be O(n/m).     

A comparison of two parallel algorithms for the symmetric eigenproblem

Two algorithms for the eigensolution of real symmetric matrices [8] are discussed. The first is a variant of the classical Jacobi method and the second is also based on orthogonal transforms. Both algorithms may be readily expressed in forms which allow the power of SIMD (single instruction multiple data) machines to be exploited. The performances of the algorithms on the ICL DAP (distributed array processor) and the CRAY-1 are compared.     

Design and implementation of parallel approximate inverse classes using OpenMP

A new parallel normalized optimized approximate inverse algorithm, based on the concept of antidiagonal wave pattern, for computing classes of explicitly approximate inverses, is introduced for symmetric multiprocessor systems. The parallel normalized explicit approximate inverses are used in conjunction with parallel normalized explicit preconditioned conjugate gradient schemes for the efficient solution of finite element sparse linear systems. The parallel design and implementation issues of the new algorithm are discussed and the parallel performance is presented using OpenMP. Copyright © 2008 John Wiley & Sons, Ltd.     

A Guass–Newton-like method for inverse eigenvalue problems

In this paper, we propose a Guass–Newton-like method for finding least-square solutions to inverse eigenvalue problems. We show that the proposed method converges under some mild conditions. In particular, if the method converges to the exact solution, the convergence rate is at least quadratic in the root sense. Numerical examples are given to justify the theoretical result.     

Parallel computation of the eigenvalues of symmetric Toeplitz matrices through iterative methods

This paper presents a new procedure to compute many or all of the eigenvalues and eigenvectors of symmetric Toeplitz matrices. The key to this algorithm is the use of the “Shift–and–Invert” technique applied with iterative methods, which allows the computation of the eigenvalues close to a given real number (the “shift”). Given an interval containing all the desired eigenvalues, this large interval can be divided in small intervals. Then, the “Shift–and–Invert” version of an iterative method (Lanczos method, in this paper) can be applied to each subinterval. Since the extraction of the eigenvalues of each subinterval is independent from the other subintervals, this method is highly suitable for implementation in parallel computers. This technique has been adapted to symmetric Toeplitz problems, using the symmetry exploiting Lanczos process proposed by Voss [H. Voss, A symmetry exploiting Lanczos method for symmetric Toeplitz matrices, Numerical Algorithms 25 (2000) 377–385] and using fast solvers for the Toeplitz linear systems that must be solved in each Lanczos iteration. The method compares favourably with ScaLAPACK routines, specially when not all the spectrum must be computed.     

New solutions to the mapping problem of parallel systems: The evolution approach

Problems concerning parallel computers can be understood and solved using results of natural sciences.

We show that the mapping problem—assigning processes to processors—can be reduced to the graph partitioning problem. We solve the partitioning problem by an evolution method derived from biology.

The evolution method is then applied to the travelling salesman problem. The competition part of the evolution method gives an almost linear speedup compared to the sequential method. A cooperation method leads to new heuristics giving better results than the known heuristics.     

Applying parallel computer systems to solve symmetric tridiagonal eigenvalue problems

A block parallel partitioning method for computing the eigenvalues of symmetric tridiagonal matrix is presented. The algorithm is based on partitioning, in a way that ensures load balance during computation. This method is applicable to both shared memory- and distributed memory-MIMD systems. Compared with other parallel tridiagonal eigenvalue algorithms existing in the literature, the proposed algorithm achieves a higher speedup of O(p) on a parallel computer with p-fold parallelism, which is linear, and the data communication between processors is less than that required for other methods. The results were tested and evaluated on an MIMD machine, and were within 62% to 98% of the predicted performance.     

A torque-canceling system using the inverse dynamics parallel solution scheme

A new torque-canceling system (TCS) that stabilizes mechanical sway of robots in motions with large inertia by considering the dynamics of the robot itself is discussed in this paper. The TCS cancels the reaction moment generated by the motion of an object by considering the precise dynamics of the object and the body of the robot itself. The dynamics and the reaction moments are calculated using an inverse dynamics parallel solution scheme that handles the dynamics of complex robotic structures by modeling them with finite elements. Once the reaction moment is known, it is canceled by applying an anti-torque to a torque-generating device. The TCS was verified by a simple experimental setup that enables rotational motion around a single axis in the previous paper. However, the effect of the TCS was not confirmed on those cases where mechanical sways are generated not only in the rotational axis of a rotor but also in the orthogonal axis. Therefore, those cases are tested to confirm the function of the TCS in multi-axial cases in this paper. Then, the TCS is mounted on a walking robot with a closed-loop structure and with a walking motion associated with boundary conditions that vary during the motion. The robot sways during its walking motion, and the validity of the TCS is verified by confirming the distances from standard landing point after a multi-step walking sequence.     

A parallel linear solver for multilevel Toeplitz systems with possibly several right-hand sides

A Toeplitz matrix has constant diagonals; a multilevel Toeplitz matrix is defined recursively with respect to the levels by replacing the matrix elements with Toeplitz blocks. Multilevel Toeplitz linear systems appear in a wide range of applications in science and engineering. This paper discusses an MPI implementation for solving such a linear system by using the conjugate gradient algorithm. The implementation techniques can be generalized to other iterative Krylov methods besides conjugate gradient. These techniques include the use of an arbitrary dimensional process grid for handling the multilevel Toeplitz structure, a communication-hiding approach for performing matrix–vector multiplications, the incorporation of multilevel circulant preconditioning for accelerating convergence, an efficient orthogonalization manager for detecting linear dependence in block iterations, and an algorithmic rearrangement to eliminate all-reduce synchronizations. The combined use of these techniques leads to a scalable solver for large multilevel Toeplitz systems, possibly with several right-hand sides. We show experimental results on matrices of size up to the order of one billion with nearly perfect scaling by using up to 1024 MPI processes. We also demonstrate an application of the solver in parameter estimation for analyzing large-scale climate data.     

A parallel variable neighborhood search approach for the obnoxious p‐median problem

The obnoxious p‐median problem consists of selecting p locations, considered facilities, in a way that the sum of the distances from each nonfacility location, called customers, to its nearest facility is maximized. This is an ‐hard problem that can be formulated as an integer linear program. In this paper, we propose the application of a variable neighborhood search (VNS) method to effectively tackle this problem. First, we develop new and fast local search procedures to be integrated into the basic VNS methodology. Then, some parameters of the algorithm are tuned in order to improve its performance. The best VNS variant is parallelized and compared with the best previous methods, namely branch and cut, tabu search, and GRASP over a wide set of instances. Experimental results show that the proposed VNS outperforms previous methods in the state of the art. This fact is finally confirmed by conducting nonparametric statistical tests.     

从头预测蛋白质骨架的一种并行蚁群方法及其在CASP8/9中的应用

从低同源关系的氨基酸序列预测蛋白质的三维结构被称为从头预测,它是计算生物学领域中的挑战之一.蛋白质骨架预测是从头预测的必要先导步骤.本文应用一种基于共享信息素的并行蚁群优化算法,在现有能量函数指导下,通过不同能量项之间的定性互补,构建具有最低能量的蛋白质骨架结构,并通过聚类选择构象候选集合中具有最低自由能的构象.在CASP8/9所公布的从头建模目标上应用了该方法,CASP8的13个从头建模目标中,模型1中有2个目标的预测结果超过CASP8中最好的结果,7个位列前10名;CASP9的29个从头建模目标中,候选集中的最佳结果中有20个进入Server组的前10名,模型1中有11个进入前10名.本文的结果说明融合多个不同的能量函数指导并行搜索,可以更好地模拟天然蛋白质的折叠行为.同时,在本算法载体上实现了不同种类搜索策略的融合并行,对于用非确定性算法解决类似的优化问题来说也是一种新颖的方法.     

A minimal communication approach to parallel time integration

We explore an approach due to Nievergelt of decomposing a time-evolution equation along the time dimension and solving it in parallel with as little communication as possible between the processors. This method computes a map from initial conditions to final conditions locally on slices of the time-domain, and then patches these operators together into a global solution using a single communication step. A basic error analysis is given, and some comparisons are made with other parallel in time methods. Based on the assumption that parallel computation is cheap but communication is very expensive, it is shown that this method can be competitive for some problems. We present numerical simulations on graphic chips and on traditional parallel clusters using hundreds of processors for a variety of problems to show the practicality and scalability of the proposed method.