Applied Math seminar: A New Asynchronous Solver for Banded Linear Systems

Where and when: Thursday October 22 at 3:30pm in Lippitt 205

Presented by:
Michael Jandron
Naval Undersea Warfare Center, Newport, RI

Anthony Ruffa
Naval Undersea Warfare Center, Newport, RI

James Baglama
Department of Mathematics, University of Rhode Island, RI

Banded linear systems occur frequently in mathematics and physics. However, direct solvers for large systems cannot be performed in parallel without communication. We will discuss a general asymmetric banded solver using a direct approach that scales across many processors efficiently. The method requires more floating point calculations than a standard solver such as LU decomposition, but by leveraging multiple processors the overall solution time is reduced. We present a solver using a superposition approach that decomposes the original linear system into q subproblems, where q is the number of superdiagonals. Each system can be solved in parallel asynchronously, followed by a qxq constraint matrix problem that is solved before a final vectorized superposition is performed. Reduction to row echelon form is not required by the solver, and hence the method can be fast and avoids fill-in when q processors are available. The algorithm is first developed for tridiagonal and pentadiagonal problems, followed by an extension to arbitrary banded systems. In addition, accuracy and performance is compared with existing solvers as well as the next avenues for this research will be discussed.

Mr. Michael Jandron is a mechanical engineer at the Naval Undersea Warfare Center since 2008 working in the areas of numerical methods, finite element analysis, and structural-acoustics. He completed a summa cum laude double major B.S. in Mechanical Engineering and Applied Mathematics from URI in 2007. Afterwards, he completed a M.S. in Solid Mechanics from Brown University in 2012 and is currently enrolled as a PhD student at Brown in the area of Solid Mechanics.