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 Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  Closed
Release:  dev Operating System:  Any

Add a New Comment(Rich Markup)
   

You are not logged in

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

 

( Jump to the original submission)

Mon 18 Jun 2018 07:53:11 PM UTC, comment #9:

I created a few bug reports to address the issues I've noted, bug #54142, bug #54143, bug #54144. There could be another one or two as well, but let's discontinue this thread and continue in the individual new reports since the other issues aren't related to nnz.

Dan Sebald <sebald>
Mon 18 Jun 2018 06:45:50 PM UTC, comment #8:

Oh, and I forgot to mention one of the first things that caught my eye, and why I started the examples with a sparse matrix. In the issorted() documentation it states

Again, sorting a sparse matrix is simply a case of changing the sparse-matrix's indeces appropriately. In fact, it's already implemented:

So why can't issorted() work for sparse matrices?

Dan Sebald <sebald>
Mon 18 Jun 2018 06:29:48 PM UTC, comment #7:

I'll give it a try. I'm a bit busy this summer, so it may take a while even though it's not that big of a changeset.

I'm a little confused with the current issorted() for full matrices. The following all looks fine:

But why can't issorted() act on a matrix?

I would think that issorted() is a counterpart to sort(), so it should be able to act on something output by sort().

Furthermore, there is this "rows" option, which refers to sortrows(). Now, I understand the idea of a sortrows(). It's a vector-based sort that maintains order across rows; a bit like a spreadsheet sort, if you follow. But it seems to me that in order to test whether this is a valid output of sortrows(), one needs to know how the sorting of sortrows() was done, i.e., the "C" of sortrows() documentation. Also, note that this works

yet without the "rows" it's the error above. And what about a "cols" counterpart? Why should vector-sorting be allowed only in the "rows" dimension?

Dan Sebald <sebald>
Mon 18 Jun 2018 03:50:39 PM UTC, comment #6:

Using the 80/20 rule, I think the biggest gains would be made by changing sort and issorted. I'm okay with leaving reshape and permute as they are.

There is some question whether this should be done in the interpreter library or in liboctave but we could punt on that for now and just do it in the interpreter.

Do you want to go ahead and convert the pseudocode to a patch?

Rik <rik5>
Project Administrator
Sun 17 Jun 2018 06:46:45 PM UTC, comment #5:

That's nice.

I'm looking back at the comments I made and remembered some of this. There is the issue that other uses of to_dense() might be avoided. That is, rather than use to_dense() and then the slower non-sparse methods, construct a dense() zeros matrix and fill in only the necessary fields. Most of these won't be major speed improvements like nnz, and I wonder how often these others get used. Nonetheless, here are some comments about each (actually making the mods means altering a header file which takes considerable time to recompile):

RESHAPE

This wouldn't be a huge speed up because I would think reshape could be somewhat fast, O(N) (I haven't tried it). However, what this routine is doing ultimately is just distributing those diagonal values to a particular set of locations that could probably be handled with a simple 2D algorithm that computes the indices appropriately. That is,

1) Determine the ultimate shape of the output matrix.
2) Construct an all-zeros matrix of that size.
3) Take the diagonal vector and distribute it within that matrix, something like

PERMUTE

This one probably doesn't matter too much. Even in the cases where the number of dimensions are expanded, e.g., permute (X, [3, 1, 2]), where X is a 2D diagonal matrix, the number of elements remain the same. So, an indexing formula approach could be used here as well, but to_dense() may be fine.

SORT

This is the one that originally caught my attention. The algorithm is simple.

1) Construct an all-zeros matrix of the same size.
2) Take the diagonal vector and distribute it either to the starting or ending position of the colum (or row) of the zeros matrix. E.g.,

ISSORTED

This one could be a considerable savings. Isn't the answer to this simply dependent on the nature of the diagonal values given we already know that everything else is zero? There are a few exceptions:

1) If the matrix size is 1 x N, the matrix is sorted along columns.
2) If the matrix size is M x 1, the matrix is sorted along rows.
3) If the matrix size is 2 x 2 and xdiag(0) < 0 and xdiag(1) > 0, the matrix is sorted.
3) If the diagonal vector is all zeros, the matrix is sorted.
4) Otherwise, the matrix is not sorted.

Dan Sebald <sebald>
Sun 17 Jun 2018 04:19:26 PM UTC, comment #4:

I pushed the modifide patch here (http://hg.savannah.gnu.org/hgweb/octave/rev/920299ced721). Dan was correct that there is no need to check for whether the object is a diagonal matrix inside the diagonal class. Speed up is 1500X for the test script.

Rik <rik5>
Project Administrator
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 Files:
   
   
Comment:
   

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
  • -email is unavailable- added by sebald (Posted a comment)
  • -email is unavailable- added by batterylow (Updated the item)
  • -email is unavailable- added by rik5 (Submitted the item)
  •  

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

    Only project members can vote.

     

     

     

    Follow 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-06-17 rik5 StatusConfirmed => Fixed
        Open/ClosedOpen => Closed
    2018-02-21 batterylow Attached File- => Added 53198.diff, #43379
        Attached File- => Added test.m, #43380

    Back to the top


    Powered by Savane 3.3