Hi All,

does any one have a reference clearly describing how to do a floating/double point count for linear sys. slovers like gauss elemination, cholesky, LU ....ect . For eg. Gauss elem. is O(N^3/3).... how does one come with this estimate ??? explanations, references appreciated ???

thnx.

Try this website http://www.nr.com/

Other good references are

Linear Algebra and Its Applications Author: Gilbert Strang

Numerical Linear Algebra Author: Lloyd Trefethen

First of all, write down your algorithm as pseudocode. Now simply count the number of operations that the algorithm is doing (per iteration of course). all operations: addition, subtraction, multiplication, and division count the same. This is not exact since multiplication has several additions inside it and division has several multiplications... But it seems reasonable to assume that all operations are the same.

Here is an example (just for illustration):

for i = 0 to P

for n = 1 to N (number of elements in array)

B(n) = a(n)*a(n-1) - 2*c(n) + 3

next n

next i

for each n you have 2 multiplications, one subtraction, and one addition = 2+1+1 = 4 operations. For all the number of elements you therefore have: 4N operations. It is at this stage that you state the order of your algorithm. In this example, its is O(4N) or simply O(N) (constants do not count). For all iterations, you have 4N(P+1) operations. (remember, if u're starting from zero, you are doing p+1 steps).

Hope that was helpful