bugGNU Octave - Bugs: bug #54142, The sort() and issorted() routines...

 
 

bug #54142: The sort() and issorted() routines for diagonal matrices isn't as fast as it should be

Submitter:  Dan Sebald <sebald>
Submitted:  Mon 18 Jun 2018 07:40:14 PM UTC
   
 
Category:  Performance Severity:  1 - Wish
Priority:  5 - Normal Item Group:  Feature Request
Status:  Confirmed Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * dev Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Wed 25 Jul 2018 06:30:08 PM UTC, comment #1: 

The place for this is in liboctave/array/DiagArray2.[h|cc].  The template for the header file can be borrowed from Array.h.  Dan's code can then be placed in DiagArray2.cc.

Rik <rik5>
Group administrator
Mon 18 Jun 2018 07:40:14 PM UTC, original submission:  

In the bug report

https://savannah.gnu.org/bugs/?53198

is an analysis of nnz for diagonal matrices, with greatly improved speed when taking into consideration how sparse the diagonal matrix is.

A similar thing can be said for sort() applied to diagonal matrices.  E.g.,


octave:1> N = 1e2;
octave:2>
octave:2> f = zeros(N,1);
octave:3> for i=1:N
>   r = rand(5000,1);
>   s = diag(r);
>   tic;
>   z = sort(s);
>   f(i)=toc;
> endfor
octave:4>
octave:4> sum(f)
ans =  23.499


It should be possible to speed up this operation by noting that we can:

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.,

x_out = zeros(N_i,N_j);
for (ivec=0; ivec<N_vec; ivec++)
  {
    if (xsparse(ivec) < 0)
      {
        if (col)
          x_out(0, ivec) = x_diag(ivec);
        else
          x_out(ivec, 0) = x_diag(ivec);
      }
    else
      {
        if (col)
          x_out(N_i-1, ivec) = x_diag(ivec);
        else
          x_out(ivec, N_j-1) = x_diag(ivec);
      }
  }


and the issorted() routine boils down to a series of logical statements:

1) If the matrix size is 2 or less along the direction of sort, use the full matrix sort.  Not much penalty is incurred by that.
2) If the diagonal vector is all zeros, the matrix is sorted.
3) Otherwise, the matrix is not sorted.

Dan Sebald <sebald>

 

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

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by rik5 (Updated the item)
  • -email is unavailable- added by sebald (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-06-19 rik5 Severity3 - Normal 1 - Wish
        Item GroupNone Feature Request
        StatusNone Confirmed

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code