Basic HTML version of Foils prepared 8 November 1995

Foil 36 Comparison of Computational Complexity between Direct and Iterative Methods

From Fox Presentation Fall 1995 CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. by Geoffrey C. Fox
Note G here is size of number of grid points in each dimension
One dimension Nx = G Direct time a G (as tridiagonal matrix) Sparse time a G.G2 = G3
Two dimensions Nx = Ny = G Direct time a G2.G2 = G4 (G2xG2 banded matrix - band size G) Sparse time a G2 (one iteration) .G2 (# iterations) = G4
Three dimensions Nx = Ny = Nz = G Direct time a G3.(G2)2 = G7 (G3xG3 banded matrix - band size G2) Sparse time a G3 (one iteration) .G2 (# iterations) =G5
SOR and conjugate gradient will make iterative methods "look better" as number of iterations proportional to G and not G2

© 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 Tue Oct 13 1998