improving Numpy dot performance by removing arrays copy

2
votes

Given a matrix QT:

% ipython
Python 2.7.3
In [3]: QT.dtype
Out[3]: dtype('float64')

In [4]: QT.__class__
Out[4]: numpy.ndarray

In [5]: QT.flags
Out[5]:
      C_CONTIGUOUS : True
      F_CONTIGUOUS : False
      OWNDATA : True
      WRITEABLE : True
      ALIGNED : True
      UPDATEIFCOPY : False

I need the results of:

QT.T * QT

Problem: Whenever I try to compute these matrices multiplication, the memory overflows and the code stop running. This happen because of the matrix copy numpy is doing behind.

Tried solutions:

First:

Q = numpy.array(QT.T, order='C')
numpy.dot(Q, QT)

Second:

QT = numpy.array(QT, order='F')
Q = numpy.array(QT.T, order='F')
numpy.dot(Q, QT)

Third:

QT = numpy.matrix(QT)
QT = QT.copy('F')
Q = numpy.matrix(QT.T)
Q = Q.copy('F')
Q.dot(QT)

However, none of them is solving.

Question

How can I operate QT.T * QT without having the memory to explode?

References

http://numpy-discussion.10968.n7.nabble.com/inplace-matrix-multiplication-td21817.html

Is there an "enhanced" numpy/scipy dot method?

Numpy dot product very slow using ints

http://www.scipy.org/PerformanceTips

2
pythonmatrixnumpyscipydot-product
1) QT.T * QT is not the same as np.dot(QT.T,QT) for ndarray types. 2) What copy are you talking about? QT.T should be a view into QT so no copy is done there - mgilson
np.dot is the same as QT.T*QT. On documentation: docs.scipy.org/doc/numpy/reference/generated/numpy.dot.html "For 2-D arrays it is equivalent to matrix multiplication" - thalesfc
About the copies, numpy.dot is coping the matrices paramenters when running the code. On scipy.org/PerformanceTips: "Although C is only 40 by 40, inspecting the memory usage during the operation of dot will indicate that a copy is being made". - thalesfc
I believe what you mean to say is that np.dot(QT.T, QT) is the code expression for the math expression QT.T * QT where * is matrix multiply. QT.T * QT is also valid python code, but it does not preform a matrix multiply. - Bi Rico
QT.T * QT is not a valid code for ndarray. Sorry I did not make myself clear. BY QT.T * QT, I mean matrix multiplication. - thalesfc

2 Answers

2
votes

Have you tried:

shape = (QT.shape[2], QT.shape[2])
result = np.zeros(shape, dtype=QT.dtype)
np.dot(QT.T,  QT, out=result)

Try running the above and see which line, if any, breaks.

1
votes

If the result won't all fit into core memory, you can put it in a memory-mapped array so that the overflow will be written to your hard disk:

shape = (QT.shape[2],)*2
result = np.memmap('result.dat', dtype=QT.dtype, mode='w+', shape=shape)
np.dot(QT.T, QT, out=result)

You may also want to take a look at this algorithm for performing out-of-core SVD on very large arrays.