[Octave-bug-tracker] [bug #53198] nnz could be improved for diagonal matrices

[Rik]

URL:
  <http://savannah.gnu.org/bugs/?53198>

                 Summary: nnz could be improved for diagonal matrices
                 Project: GNU Octave
            Submitted by: rik5
            Submitted on: Tue 20 Feb 2018 10:11:33 PM PST
                Category: Octave Function
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: Performance
                  Status: Confirmed
             Assigned to: None
         Originator Name: 
        Originator Email: 
             Open/Closed: Open
         Discussion Lock: Any
                 Release: dev
        Operating System: Any

    _______________________________________________________

Details:

nnz for diagonal matrices is implemented in
libinterp/octave-value/ov-base-diag.h.  The code is simple


  octave_idx_type nnz (void) const { return to_dense ().nnz (); }


However, this isn't very efficient.  It converts and then caches the full
version of the matrix and then calls nnz on that full matrix.  Besides the
conversion, nnz on a full matrix means looking at every element.  For a
diagonal matrix nnz should just need to look at the elements on the diagonal.

For a square matrix the difference is O(N^2) for full matrix versus O(N) for
just the diagonal.







    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?53198>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/