[Octave-bug-tracker] [bug #54142] The sort() and issorted() routines for diagonal matrices isn't as fast as it should be

[Dan Sebald]

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

                 Summary: The sort() and issorted() routines for diagonal
matrices isn't as fast as it should be
                 Project: GNU Octave
            Submitted by: sebald
            Submitted on: Mon 18 Jun 2018 07:40:14 PM UTC
                Category: Performance
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: None
                  Status: None
             Assigned to: None
         Originator Name: 
        Originator Email: 
             Open/Closed: Open
         Discussion Lock: Any
                 Release: dev
        Operating System: Any

    _______________________________________________________

Details:

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.




    _______________________________________________________

Reply to this item at:

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

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