[Octave-bug-tracker] [bug #64718] symrcm very slow, scales cubically instead of sub-quadratically

[Arun Giridhar]

Update of bug #64718 (project octave):

                  Status:                    None => Ready For Test         

    _______________________________________________________

Follow-up Comment #1:

This attempt is much closer to expectations:


octave:1> clear all; for n = 1:5, adj = ~eye (n * 1e3); adj *= (1-i); tic; p =
symrcm (adj); t(n) = toc; disp ([n t(n)]); end
   1.000000   0.098254
   2.0000   0.4165
   3.0000   0.9101
   4.0000   1.7312
   5.0000   2.7354

octave:2> t / t(1)
ans =
    1.0000    4.2395    9.2631   17.6198   27.8402


It's about 100x faster for N = 5000 and also scales quadratically instead of
cubically, for a dense matrix. (For sparser inputs, it's closer to linear).

There was also a minor error for an all-zeros input. The output was supposed
to be 1:N, but it was returning 0:(N-1). That's been fixed too.

Added two BISTs.

Pushed to https://hg.savannah.gnu.org/hgweb/octave/rev/4de460f3ffe0

Ready for test.


    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?64718>

_______________________________________________
Message sent via Savannah
https://savannah.gnu.org/