[seqfan] Computational Efficiency Sequences

[Brad Klee]

Hi Seqfans,

Just wondering if there are any sequences in the OEIS related to
computational efficiency? If so maybe there should be a list referencing
these series.

I did a quick search, but found nothing. More thesis work led me to compute
the sequence for number of { multiply, divide, add, subtract} operations
required to solve a system of N linear equations, assuming all symbolic
terms. That sequence is not in the OEIS ( derivation below ).

Look at the following list:

http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions

The approximate O sequences could be replaced by exact sequences as I have
( possibly ) done for solving a determined system of linear equations.

I guess the main difficulty is to arrive at a canonical form for the
algorithm and a consistent method for counting operations. But given the
importance of computer time, I'm sure that these sequences would be of some
practical interest.

Any ideas?

Derivation of sequence for counting the maximum number of arithmetic
operations required to solve a linear system of equations with exactly one
solution:

Each term of the sequence

2, 9, 29, 68, 132, 227, 359, 534, 758, 1037, 1377, 1784, 2264, 2823,
3467, 4202, 5034, 5969, 7013, 8172...

is the value of

2 - (3n)/2 + n^2/2 + n^3,

which can be computed by summation after the operation count at each
iteration of the algorithm has been determined. The algorithm is
row-reduction of a N X (N+1) matrix.

Starting with n = N

At each iteration:

1. Set leading non-zero number to 1
Divide n+1 numbers by M[ N-n+1, N-n+1 ]
2. Eliminate other numbers in the same column
multiply and subtract from n elements in N-1 rows
(skip N-1 multiplications and subtractions of the form a - 1*a = 0)
3. Set n' = n - 1
(do not count operations on indices)

Halt if n=2 otherwise Iterate

Finally, divide two numbers by M[N,N].

To compute the function, evaluate the following:

2 + Sum_{n=2}^{N} (n+1) +2 n (N - 1)
=2 - (3n)/2 + n^2/2 + n^3.

As expected this exact function equals approximately O(n^3).



Please send questions, comments, or corrections.

Thanks,

Brad