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

[Arun Giridhar]

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

                 Summary: symrcm very slow, scales cubically instead of
sub-quadratically
                   Group: GNU Octave
               Submitter: arungiridhar
               Submitted: Tue 26 Sep 2023 10:09:25 AM EDT
                Category: Octave Function
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: Performance
                  Status: None
             Assigned to: None
         Originator Name: 
        Originator Email: 
             Open/Closed: Open
                 Release: dev
         Discussion Lock: Any
        Operating System: Any
           Fixed Release: None
         Planned Release: 9.1.0 (current default)


    _______________________________________________________

Follow-up Comments:


-------------------------------------------------------
Date: Tue 26 Sep 2023 10:09:25 AM EDT By: Arun Giridhar <arungiridhar>
Found that symrcm takes cubic time in the order of the input matrix, which
should not happen at all.


octave:3> clear all; for n = 1:5, adj = ~eye (n * 1e3); tic; p = symrcm (adj);
t(n) = toc; disp ([n t(n)]); end
                       1       2.047679901123047
                       2       16.45807313919067
                       3        55.5030460357666
                       4       131.9801509380341
                       5       258.6089651584625

octave:4> t / t(1)
ans =
                       1       8.037424760659256       27.10533321410541      
64.45350704748812       126.2936482487467


Now, symrcm is just a fancy BFS and BFS should take only O(V+E) at worst, so
no more than quadratic time in V even if the matrix is very dense.

On instrumenting symrcm.cc with std::chrono, it looked like the majority of
the time spent is *not* in the BFS itself, but in the function calc_degrees
before the BFS even begins. The purpose of calc_degrees is to calculate the
vertex degrees of each row/column, which again should take only O(E) time, not
O(V^3) time.

To compare, calculating the vertex degrees of a 5000 x 5000 sparse matrix this
way:


octave:2> tic; A = sparse (~eye (5000)); toc, tic; d = sum (A); toc
Elapsed time is 0.179053 seconds.
Elapsed time is 3.98159e-05 seconds.
-verbatim0

takes only 40 microseconds, not over 4 minutes, so something is badly wrong
with calc_degrees the way it is written with three nested loops (which
explains why it's cubic).

I'll get to fixing that function this week.







    _______________________________________________________

Reply to this item at:

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

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