[seqfan] Re: Computational Efficiency Sequences

[Giovanni Resta]

On 05/18/2015 04:25 AM, Brad Klee wrote:

> Reviewing my sequence from earlier, it seems possible to further reduce the
> number of operations by skipping the first division at every iteration. It
> is always the case that "a / a = 1".

In general, like Robert Israel already pointed out, you must be very
careful in stating something like:

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

because the number of operations *required* to solve a linear system
is actually unknown, i.e., the *computational complexity* of linear 
systems solution is unknown. (This is true for almost all the 
interesting problems...)

What you can "count", is the *computational cost* (best case, worst 
case, average case, amortized case, etc.etc) of solving a linear
system using a very specific algorithm, in a very specific computational 
model (sequenzial, paralled, determistic, nondetermistic, 
randomized,etc.), using a specific way to measure the cost (all 
operations, just arithmetic, only * and /, swaps, etc.etc.).

The fact that this cost (seen as a precise numbers instead of something 
like O(n^3 log(n))), depends on so many parameters could make
it difficult to decide on which variant to focus to build a useful sequence.

Giovanni