bugGNU Octave - Bugs: bug #53198, nnz could be improved for diagonal...


bug #53198: nnz could be improved for diagonal matrices

Submitted by:  Rik <rik5>
Submitted on:  Wed 21 Feb 2018 06:11:33 AM UTC  
Category: Octave FunctionSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Performance
Status: ConfirmedAssigned to: None
Originator Name: Open/Closed: Open
Release: devOperating System: Any

Add a New Comment(Rich Markup)

You are not logged in

Please log in, so followups can be emailed to you.


Wed 21 Feb 2018 09:25:54 PM UTC, comment #3:

I've applied a second test with

And I don't see any consequence of the patch

I take it that in this scenario:

the matrix representation is some other class that has a fast implementation of nnz(). So that's good.

One other note: be sure to check changesets for any dangling whitespace. If you are running linux, type "hg diff" at a bash shell and you are likely to see highlighted red blocks wherever there is whitespace after the last character.

Dan Sebald <sebald>
Wed 21 Feb 2018 08:01:14 PM UTC, comment #2:

I've looked at the patch. The conditional test

if (is_diag_matrix ())

in the patch appears to be superfluous. Isn't the class, by definition, diagonal? Wouldn't simply extracting the diagonal, i.e., collapsing to a vector, be sufficient? I.e.,

However, there is some special code in the ::diag() method:

Is that special case something to be concerned about? I think that would arise for the following sort of construct:

(Note how the application of diag() with k=0, the default in calling the ::diag() member function, expands the matrix in this case, not contracts it.)

Also, throughout ov-base-diag.h are several to_dense() calls. Maybe they all could be addressed with one patch here. For example, there is the method "sort" that uses to_dense() first, but that too could be improved speed-wise noting that the operation boils down to pushing the diagonal value either to the first or last row, WLOG, e.g.,

(if it is sort-by-row, then change the rule for the other direction). One would just start with the appropriately sized zeros matrix and then index through the diagonal vector sending the values to the top or bottom row based on one less-than-zero comparison.

Dan Sebald <sebald>
Wed 21 Feb 2018 06:03:05 PM UTC, comment #1:

Indeed the time difference is huge.

I tried the following test script:

Got a total time of 0.0039184 seconds with the patch applied and 11.160 seconds without the patch.

Hope this helps :)

(file #43379, file #43380)

Sahil Yadav <batterylow>
Wed 21 Feb 2018 06:11:33 AM UTC, original submission:

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

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.

Rik <rik5>
Project Administrator


(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):

Attached Files
file #43379:  53198.diff added by batterylow (909B - text/x-patch)
file #43380:  test.m added by batterylow (118B - text/x-objcsrc)


Depends on the following items: None found

Items that depend on this one: None found


Carbon-Copy List
  • -unavailable- added by sebald (Posted a comment)
  • -unavailable- added by batterylow (Updated the item)
  • -unavailable- added by rik5 (Submitted the item)

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.


    Please enter the title of George Orwell's famous dystopian book (it's a date):



    Follow 2 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Wed 21 Feb 2018 06:03:05 PM UTCbatterylowAttached File-=>Added 53198.diff, #43379
      Attached File-=>Added test.m, #43380

    Back to the top

    Powered by Savane 3.1-cleanup1