Go backward to Block-Oriented Algorithm Go up to Top Go forward to References

Analysis of Algorithm

• Row-Column-oriented algorithm
  • Computation: $n2/p*n/p\; =\; n3/p2$.
  • Communication: $2($lambda + beta n²/p)
  • $p$ iterations.
• Block-oriented algorithm
  • Computation: $n2/p*n/p\; =\; n3/p2$.
  • Communication: $4($lambda + beta n²/p)
  • $p-1$ iterations.
• Comparison

  $2p\; ($lambda + beta n²/p) > 4 ( p -1) (lambda + beta n²/p)
  $$lambda p + beta n² > 4 lambda ( p -1) + 4 beta ( p -1) n²/p

  1. $p\; >\; 4\; ($sqrt p-1) -> p > 4
  2. $1\; >\; 4\; ($sqrt p-1)/p -> p > 4