[seqfan] Re: Computational Efficiency Sequences
Giovanni Resta
g.resta at iit.cnr.it
Mon May 18 14:51:46 CEST 2015
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
More information about the SeqFan
mailing list