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

[Dan Sebald]

Follow-up Comment #5, bug #53198 (project octave):

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

  octave_value reshape (const dim_vector& new_dims) const
  { return to_dense ().reshape (new_dims); }


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


x_out = zeros(N_i,N_j);
for (i=0; i<N_i; i+=S_i)
  {
    for (j=0; j<N_j; j+=S_j)
      {
        x_out(i,j) = x_diag(i_diag++);
      }
  }



PERMUTE

  octave_value permute (const Array<int>& vec, bool inv = false) const
  {
    if (vec.numel () == 2
        && ((vec.xelem (0) == 1 && vec.xelem (1) == 0)
            || (vec.xelem (0) == 0 && vec.xelem (1) == 1)))
      return DMT (matrix);
    else
      return to_dense ().permute (vec, inv);
  }


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

  octave_value sort (octave_idx_type dim = 0, sortmode mode = ASCENDING)
const
  { return to_dense ().sort (dim, mode); }
  octave_value sort (Array<octave_idx_type> &sidx, octave_idx_type dim = 0,
                     sortmode mode = ASCENDING) const
  { return to_dense ().sort (sidx, dim, mode); }


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


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);
      }
  }



ISSORTED

  sortmode issorted (sortmode mode = UNSORTED) const
  { return to_dense ().issorted (mode); }


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.


    _______________________________________________________

Reply to this item at:

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

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