NTRS - NASA Technical Reports Server

Back to Results
Ordering Unstructured Meshes for Sparse Matrix Computations on Leading Parallel SystemsThe ability of computers to solve hitherto intractable problems and simulate complex processes using mathematical models makes them an indispensable part of modern science and engineering. Computer simulations of large-scale realistic applications usually require solving a set of non-linear partial differential equations (PDES) over a finite region. For example, one thrust area in the DOE Grand Challenge projects is to design future accelerators such as the SpaHation Neutron Source (SNS). Our colleagues at SLAC need to model complex RFQ cavities with large aspect ratios. Unstructured grids are currently used to resolve the small features in a large computational domain; dynamic mesh adaptation will be added in the future for additional efficiency. The PDEs for electromagnetics are discretized by the FEM method, which leads to a generalized eigenvalue problem Kx = AMx, where K and M are the stiffness and mass matrices, and are very sparse. In a typical cavity model, the number of degrees of freedom is about one million. For such large eigenproblems, direct solution techniques quickly reach the memory limits. Instead, the most widely-used methods are Krylov subspace methods, such as Lanczos or Jacobi-Davidson. In all the Krylov-based algorithms, sparse matrix-vector multiplication (SPMV) must be performed repeatedly. Therefore, the efficiency of SPMV usually determines the eigensolver speed. SPMV is also one of the most heavily used kernels in large-scale numerical simulations.
Document ID
Document Type
Preprint (Draft being sent to journal)
Oliker, Leonid
(National Energy Research Supercomputer Center Berkeley, CA United States)
Li, Xiaoye
(National Energy Research Supercomputer Center Berkeley, CA United States)
Heber, Gerd
(Cornell Univ. Ithaca, NY United States)
Biswas, Rupak
(MRJ Technology Solutions Moffett Field, CA United States)
Date Acquired
September 7, 2013
Publication Date
January 1, 2000
Subject Category
Computer Systems
Meeting Information
Funding Number(s)
PROJECT: RTOP 519-40-12
Distribution Limits
Work of the US Gov. Public Use Permitted.

Available Downloads

NameType 20000101664.pdf STI
No Preview Available