[seqfan] Re: Computational Efficiency Sequences

[israel at math.ubc.ca]

It's the number of operations required for solving the system by row 
reduction, but there are more efficient algorithms based on fast 
matrix-multiplication methods. See e.g. Petkovic and Stanimirovic, 
"Generalized matrix inversion is not harder than matrix multiplication", 
Journal of Computational and Applied Mathematics 230 (2009) 270-282
 <http://www.sciencedirect.com/science/article/pii/S0377042708006237>
We don't know, and are not likely to know any time soon, the actual minimum
numbers of operations as a function of N.

Cheers,
Robert


On May 17 2015, Brad Klee wrote:

>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
>
>_______________________________________________
>
>Seqfan Mailing list - http://list.seqfan.eu/
>
>