• LinAlg? framework - time spent writing new solutions is down time. No results are possible. This makes improving the software very difficult, sometimes to the point of getting grants just to develop the software. This requires that the software be more general, which increases the development down time, etc.
  • Dependent theory: software engineering, quailty control, language analysis.
  • Explored: Well. MATLAB, netlib, variety of libraries. More recently, ScaLAPACK? , PETSc, POOMA, Blitz++, Trillinos
  • difficulty for community - moderate, requires domain knowledge of mathematics and parallel software engineering
  • difficulty for you - moderate. We have the skills and experience needed
  • R vs D - development
  • risk - low. Given enough human resources, a team of 3-5 programmers could implement this package in a year.
  • impact - medium to low. A well deployed framework could do well, but it has lots of pre-existing competition.
  • human resources - medium

Parallel Linear Algebra

_Most problems in scientific computation can be reduced to an equivalent problem in linear algebra. Therefore, problems in a variety of fields are often solved first using some sort of linear algebra package, then recoded with more complex algorithms as the need arises. This is why most RAD platforms in numerical analysis, such as MATLAB and PETSc, are based in numerical linear algebra.

Linear algrebra is a perfect canidate for parallelization because it requires massive amounts of memory and computation time. However, even the most successful frameworks availiable for parallel matrix manipulation are based on MPI an older technologies.

I propose that we develop a numerical linear algebra package for charm++, as this is where our skills and techniques lie. I believe that this package would greatly increase the usability of charm++, and I belive charm++'s advanced capabilties would allow our new package to outstrip other parallel numerical linear algebra packages.

Parallel strategies for linear systems of equations

Parallel algorithms for indefinite linear systems

Preconditioning techniques for large linear systems: a survey

• statement of area
  • parallel numerical linear algebra
• why we chose our approach
  • Rob experienced in numerical analysis
  • Chao Mei experienced in parallel debugging and implementation
  • both experienced in engineering
• why important -- examples
  • google
  • structual mechanics
  • computational biology
  • justify -- not the best, just the easiest
• impact of research
  • decrease overall development time (for engineers)
  • brings supercomputing to the masses (of engineers)
• conditions for success
  • easy to use
  • fast
  • scalable
• an approach 1. develop matrix algebra package on charm++ 1. develop new parallel algorithms that decrease dependencies/improve scalabilty 1. develop new out-of-core capabilties that ease memory burdens
• who's interested
  • all scientific computation!
• what's been done
  • Pestc
  • scaLAPACK
  • parallel matlab

Materials needed

• Examples that work (Rob)
• Current research (Rob)
• new ways to tackle memory burdens (ChaoMei? )
  • out of core
  • parallel IO
• New algoritms (Rob)
  • chaotic relaxation
  • work with kirby
  • matrix-free operations

References:

• Austin06: David Austin, "How Google finds your needle in the web's haystack". Featured Column from AMS, December 2006, http://www.ams.org/featurecolumn/archive/pagerank.html
• http://arrhythmia.hofstra.edu/
• Parallel MATLAB: Doing it Right

• http://www-unix.mcs.anl.gov/petsc/petsc-as/
• http://www.netlib.org/scalapack/scalapack_home.html
• Development of Naturally Fault Tolerant Algorithms for Computing on 100,000 Processors
  • Al Geist
  • Christian Engelmann
  • 2002
  • Oak Ridge National Laboratory
• A. Frommer and D.B. Szyld, On asynchronous iterations, Journal of Comp. and Appl. Math., 123 (2000), pp. 201-216.