Basic HTML version of Foils prepared 15 March 1996

Foil 17 Computational Complexity of Solution of ADI Equations

From Spatial Differencing and ADI Solution of the NAS Benchmarks CPSP713 Case studies in Computational Science -- Spring Semester 1996. by Geoffrey C. Fox
1 The original nonfactorized equations were sparse matrices with bandwidth L=(2N 2NAS+1)
2 Solving equations with M rows and columns and bandwidth L takes ML2 operations
3 This gives original complexity for M=N 3NAS proportional to N 7NAS
4 A tridiagonal matrix has bandwidth 3 and so complexity of ADI factorized equations is just proportional to M or N 3NAS
5 Effect of 5 by 5 blocks:
  • This implies that every operation is that of 5 by 5 matrix vector multiplication or matrix/vector addition i.e. one increases estimate by roughly 53 or 125.
in Table To:

Northeast Parallel Architectures Center, Syracuse University, npac@npac.syr.edu

If you have any comments about this server, send e-mail to webmaster@npac.syr.edu.

Page produced by wwwfoil on Sun Feb 22 1998