vectorized linalg

Tim Hochberg tim.hochberg at ieee.org
Mon Oct 9 09:45:37 CDT 2006


David Goldsmith wrote:
> Tim Hochberg wrote:
>   
>> I periodically need to perform various linalg operations on a large 
>> number of small matrices. The normal numpy approach of stacking up the 
>> data into an extra dimension and doing the operations in parallel 
>> doesn't work because the linalg functions are only designed to work on 
>> one matrix at a time. At first glance, this restriction seems harmless 
>> enough since the underlying LAPACK functions are also designed to work 
>> one matrix at a time and it seem that there would be little to be gained 
>> by parallelizing the Python level code. However, this turns out to be 
>> the case.
>>
>> I have some code, originally written for numarray, but I recently ported 
>> it over to numpy, that rewrites the linalg function determinant, inverse 
>> and solve_linear_equations[1] to operate of 2 or 3D arrays, treating 3D 
>> arrays as stacks of 2D arrays. For operating on large numbers of small 
>> arrays (for example 1000 2x2 arrays), this approach is over an order of 
>> magnitude faster than the obvious map(inverse, threeDArray) approach.
>>
>> So, some questions:
>>
>>     1. Is there any interest in this code for numpy.linalg? I'd be 
>> willing to clean it up and work on the other functions in linalg so that 
>> they were all consistent. Since these changes should all be backwards 
>> compatible (unless your counting on catching an error from one of the 
>> linalg functions), I don't see this as a problem to put in after 1.0, so 
>> there's really no rush on this. I'm only bringing it up now since I just 
>> ported it over to numpy and it's fresh in my mind.
>>   
>>     
> Say "no" to someone offering to make a Python module more feature rich?  
> Blasphemy! :-)
>
> But I am very curious as to the source/basis of the performance 
> improvement - did you figure this out?
>   
Yes and no. Here's what the begining of linalg.det looks lik:

    a = asarray(a)
    _assertRank2(a)
    _assertSquareness(a)
    t, result_t = _commonType(a)
    a = _fastCopyAndTranspose(t, a)
    n = a.shape[0]
    if isComplexType(t):
        lapack_routine = lapack_lite.zgetrf
    else:
        lapack_routine = lapack_lite.dgetrf
    # ...

There's quite a few function calls here, since the actual call to dgetrf 
probably takes neglible time for a 2x2 array, the cost of computation 
here is dominated by function call overhead, creating the return arrays 
and such not. Which is the biggest culprit, I'm not sure; by vectorizing 
it, much of that overhead is only incurred once rather than hundreds or 
thousands of times, so it all becomes negligible at that point. I didn't 
bother to track down the worst offender.


-tim




-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys -- and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV




More information about the Numpy-discussion mailing list