Narrow Results

In this paper we discuss different approaches for exploiting parallelism in the ICCG method for solving large sparse symmetric positive definite systems of equations on a shared memory parallel computer. Techniques for efficiently solving triangular systems and computing sparse matrix-vector products are explored. Three methods for scheduling the tasks in solving triangular systems are implemented on the Sequent Balance 21000. Sample problems that are representative of a large class of problems solved using iterative methods are used. We show that a static analysis to determine data dependences in the triangular solve can greatly improve its parallel efficiency. We also show that, under certain circumstances, ignoring symmetry and storing all nonzero elements of a sparse matrix can reduce solution time substantially.

The Lanczos method has rapidly become the preferred method of solution for the generalized eigenvalue problems. The recent emergence of parallel computers has aroused much interest in the practical implementation of the Lanczos algorithm on these high performance computers. This paper describes an implementation of a generalized Lanczos algorithm on a distributed memory parallel computer, with specific application to structural dynamic analysis.

One major cost in the parallel implementation of the generalized Lanczos procedure is the factorization of the (shifted) stiffness matrix and the forward and backward solution of triangular systems. In this paper, we review a parallel sparse matrix factorization scheme and propose a strategy for inverting the principal block submatrix factors to facilitate the forward and backward solution of triangular systems on distributed memory parallel computers. We also discuss the different strategies in the implementation of mass-matrix-vector multiplication and how they are used in the implementation of the Lanczos procedure. The Lanczos procedure implemented includes partial and external selective reorthogonalizations. Spectral shifts are introduced when memory space is not sufficient for storing the Lanczos vectors. The tradeoffs between spectral shifts and Lanc-zos iterations are discussed. Numerical results on Intel’s parallel computers, the iPSC/860 hypercube and the Paragon machines will be presented to illustrate the effectiveness and scalability of the parallel generalized Lanczos procedure.

The parallel simulation of Spiking Neural P systems is mainly based on a matrix representation, where the graph inherent to the neural model is encoded in an adjacency matrix. The simulation algorithm is based on a matrix-vector multiplication, which is an operation efficiently implemented on parallel devices. However, when the graph of a Spiking Neural P system is not fully connected, the adjacency matrix is sparse and hence, lots of computing resources are wasted in both time and memory domains. For this reason, two compression methods for the matrix representation were proposed in a previous work, but they were not implemented nor parallelized on a simulator. In this paper, they are implemented and parallelized on GPUs as part of a new Spiking Neural P system with delays simulator. Extensive experiments are conducted on high-end GPUs (RTX2080 and A100 80GB), and it is concluded that they outperform other solutions based on state-of-the-art GPU libraries when simulating Spiking Neural P systems.

This paper presents an integrated approach to two issues relevant to efficient parallel sparse Cholesky factorization: 1) matrix reordering for parallelism, and, 2) mapping of data to processors. A clustering heuristic is proposed to performs a fill-preserving reordering and mapping of data onto a fixed number of processors. Performance results on a Cray T3D are presented to demonstrate its effectiveness.

We propose a framework for compressive sensing of images with local distinguishable objects, such as stars, and apply it to solve a problem in celestial navigation. Specifically, let x ∈ ℝ^N be an N pixel image, consisting of a small number of local distinguishable objects plus noise. Our goal is to design an m × Nmeasurement matrix A with m ≪ N, such that we can recover an approximation to x from the measurements Ax.

We construct a matrix A and recovery algorithm with the following properties: (i) if there are k objects, the number of measurements m is O((k log N)/(log k)), undercutting the best known bound of O(k log (N/k)) (ii) the matrix A is very sparse, which is important for hardware implementations of compressive sensing algorithms, and (iii) the recovery algorithm is empirically fast and runs in time polynomial in k and log(N).

We also present a comprehensive study of the application of our algorithm to attitude determination, or finding one's orientation in space. Spacecraft typically use cameras to acquire an image of the sky, and then identify stars in the image to compute their orientation. Taking pictures is very expensive for small spacecraft, since camera sensors use a lot of power. Our algorithm optically compresses the image before it reaches the camera's array of pixels, reducing the number of sensors that are required.

We propose a simple and direct node shifting method with hill climbing for the well-known matrix bandwidth minimization problem. Many heuristics have been developed for this NP-complete problem including the Cuthill-McKee (CM) and the Gibbs, Poole and Stockmeyer (GPS) algorithms. Recently, heuristics such as Simulated Annealing, Tabu Search and GRASP have been used, where Tabu Search and the GRASP with Path Relinking achieved significantly better solution quality than the CM and GPS algorithms. Experimentation shows that our method achieves the best solution quality when compared with these while being much faster than newly-developed algorithms.