[Octave-bug-tracker] [bug #60577] Detect (sparse) transposed lower triangular linear systems

[Marco Caliari]

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

                 Summary: Detect (sparse) transposed lower triangular linear
systems
                 Project: GNU Octave
            Submitted by: caliari
            Submitted on: Tue 11 May 2021 06:55:54 AM UTC
                Category: Interpreter
                Severity: 2 - Minor
                Priority: 5 - Normal
              Item Group: Performance
                  Status: None
             Assigned to: None
         Originator Name: 
        Originator Email: 
             Open/Closed: Open
                 Release: 6.1.0
         Discussion Lock: Any
        Operating System: GNU/Linux

    _______________________________________________________

Details:

If I run the following code with M sparse or full


m = 500;
M = toeplitz(sparse([1,1],[1,2],[4,1],1,m));
R = chol(M); % try it with chol(full(M));
b = randn(m,1);
tic
for i = 1:10000
  R\b;
end
toc
tic
for i = 1:10000
  R'\b;
end
toc


I observe the transposed system 1.5x slower than the untransposed one in the
sparse case, while there is no difference in the full case. I have two
possible explanations:
1) in the full case the interpreter detects that R' is lower triangular and
avoids transposition
2) in the full case the computational cost hides the cost related to
transposition

Would it be possible to detect in any case that R' is lower triangular and
avoid transposition?




    _______________________________________________________

Reply to this item at:

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

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