Opened 6 years ago

Closed 4 years ago

#20679 closed enhancement (wontfix)

matrix vector product for generic sparse matrices

Reported by: orkolorko Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: linear algebra Keywords: sparse, product
Cc: Merged in:
Authors: Vincent Delecroix Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by tscrim)

It seems like this simple cython code is faster 30% faster than the implemented matrix vector product for generic sparse matrices. I run some tests with matrices with RIF coefficients and all seem to point in this direction.

%cython file
import cython

from sage.matrix.matrix_generic_sparse cimport *
from sage.modules.free_module_element cimport *

# this is a generic sparse_mat_vec,
# hoping to get some speedup from the fact that it is compiled
def cython_sparse_matvec(Matrix_generic_sparse P,
                         FreeModuleElement_generic_dense v,
                         FreeModuleElement_generic_dense w):
  for (ij, val) in P.dict().iteritems():
    w[ij[0]] += val*v[ij[1]]

def cython_sparse_vecmat(Matrix_generic_sparse P,
                         FreeModuleElement_generic_dense v,
                         FreeModuleElement_generic_dense w):
  for (ij, val) in P.dict().iteritems():
    w[ij[1]] += val*v[ij[0]]

%python module
def sparse_matvec(P,v):
  """
  Compute Sage sparse matrix * vector product.

  Apparently, M*v fills the matrix in Sage, so this should be quicker
  """
  w = VectorSpace(P.base_ring(),P.nrows())(0)
  cython_sparse_matvec(P,v,w)
  return w


def sparse_vecmat(v,P):
  """
  Compute Sage sparse vector * matrix product.

  Apparently, v*M fills the matrix in Sage, so this should be quicker
  """
  w = VectorSpace(P.base_ring(),P.ncols())(0)
  cython_sparse_vecmat(P,v,w)
  return w

Change History (3)

comment:1 Changed 4 years ago by tscrim

  • Description modified (diff)
  • Milestone changed from sage-7.3 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

This is how the matrix action on vectors is currently (8.1.beta9) implemented. So either this ticket description is out of date or the speedup is due to skipping safety checks. Without timings and an example, it is hard to determine. I propose to close since the proposal is functionally no change.

comment:2 Changed 4 years ago by vdelecroix

  • Authors set to Vincent Delecroix
  • Status changed from needs_review to positive_review

comment:3 Changed 4 years ago by vdelecroix

  • Resolution set to wontfix
  • Status changed from positive_review to closed

closing positively reviewed duplicates

Note: See TracTickets for help on using tickets.