Search

In this paper, we revisit the Krylov multisplitting algorithm presented in Huang and O'Leary (Linear Algebra Appl 194:9-29, ) which uses a sequential method to minimize the Krylov iterations computed by a multisplitting algorithm. Our new algorithm is based on a parallel multisplitting algorithm with few blocks of large size using a parallel GMRES method inside each block and on a parallel Krylov minimization to improve the convergence. Some large-scale experiments with a 3D Poisson problem are presented with up to 8,192 cores. They show the obtained improvements compared to a classical GMRES both in terms of number of iterations and in terms of execution times. [ABSTRACT FROM AUTHOR]

Loop tiling and unrolling are two important program transformations to exploit locality and expose instruction level parallelism, respectively. However, these transformations are not independent and each can adversely affect the goal of the other. Furthermore, the best combination will vary dramatically from one processor to the next. In this paper, we therefore address the problem of how to select tile sizes and unroll factors simultaneously. We approach this problem in an architecturally adaptive manner by means of iterative compilation, where we generate many versions of a program and decide upon the best by actually executing them and measuring their execution time. We evaluate several iterative strategies based on genetic algorithms, random sampling and simulated annealing. We compare the levels of optimization obtained by iterative compilation to several well-known static techniques and show that we outperform each of them on a range of benchmarks across a variety of architectures. Finally, we show how to quantitatively trade-off the number of profiles needed and the level of optimization that can be reached. In this way, we can reach high levels of optimization within 50 iterations. [ABSTRACT FROM AUTHOR]

This paper develops an algorithm for iterative learning control on the basis of the quasi-Newton method for nonlinear systems. The new quasi-Newton iterative learning control scheme using the rank-one update to derive the recurrent formula has numerous benefits, which include the approximate treatment for the inverse of the system's Jacobian matrix. The rank-one update-based ILC also has the advantage of extension for convergence domain and hence guaranteeing the choice of initial value. The algorithm is expressed as a very general norm optimization problem in a Banach space and, in principle, can be used for both continuous and discrete time systems. Furthermore, a detailed convergence analysis is given, and it guarantees theoretically that the proposed algorithm converges at a superlinear rate. Initial conditions which the algorithm requires are also established. The simulations illustrate the theoretical results. [ABSTRACT FROM AUTHOR]

Solving large sparse linear systems is essential in numerous scientific domains. Several algorithms, based on direct or iterative methods, have been developed for parallel architectures. On distributed grids consisting of processors located in distant geographical sites, their performance may be unsatisfactory because they suffer from too many synchronizations and communications. The GREMLINS code has been developed for solving large sparse linear systems on distributed grids. It implements the multisplitting method that consists in splitting the original linear system into several subsystems that can be solved independently. In this paper, the performance of the GREMLINS code obtained with several libraries for solving the linear subsystems is analyzed. Its performance is also compared with that of the widely used PETSc library that enables one to develop portable parallel applications. Numerical experiments have been carried out both on local clusters and on distributed grids. [ABSTRACT FROM AUTHOR]

Pricing of derivatives is one of the central problems in computational finance. Since the theory of derivative pricing is highly mathematical, numerical techniques such as lattice approach, finite-difference and finite-element among others have been employed. Recently fast Fourier transform (FFT) has been employed for derivative pricing in sequential computers. In this paper, we report development of a multithreaded FFT pricing algorithm and performance evaluation on a multithreaded platform. The focus of this study is on the effectiveness of using a parallel computer for financial problems and performance evaluation of a multithreaded algorithm for finance applications such as derivative pricing. In general, a parallel algorithm for FFT, with blocked data distribution of N elements on P processors, involves communication for log P iterations and terminates after log N iterations. The first (log N - log P) iterations therefore, require no communication and a sequential algorithm can be used in each processor. We call this a local algorithm. At the end of the (log N - log P) iterations, the processors switch to a multithreaded algorithm where sending and receiving of threads is through message passing. We call this a remote algorithm. The algorithm has been implemented on the EARTH (Efficient Architecture for Running THreads) multithreaded platform. Our results indicate that the FFT multithreaded algorithm for option pricing is very efficient giving a relative speedup of 50% on 64 processors. This study reveals an important commercial application for High Performance Computing. [ABSTRACT FROM AUTHOR]

This article presents an algorithm that performs a decentralized detection of the global convergence of parallel asynchronous iterative applications. This algorithm is fault tolerant. It runs a decentralized saving procedure which enables this algorithm, after a node’s crash, to replace the dead node by a new one which will continue the computing task from the last check point. Combined with the advantages of the asynchronous iteration model, this method allows us to compute very large scale problems using highly volatile parallel architectures like Peer-to-Peer and distributed clusters architectures. We also present the implementation of this algorithm in the JaceP2P platform which is dedicated to designing and executing parallel asynchronous iterative applications in volatile environments. Numerous experiments show the robustness and the efficiency of our algorithm. [ABSTRACT FROM AUTHOR]