Skip to content

np.dot(a, a.T) should be detected and dispatched to the BLAS syrk routine #6794

Closed

Description

@njsmith

BLAS provides a specialized routine for the common A @ A.T operation. We should detect this case (same data pointer, reversed strides) and dispatch to syrk instead of gemm. (see)

In addition to providing a nice speedup, this should presumably avoid issues like #6793, where dot(A, A.T) returned a non-exactly-symmetric matrix and this caused confusion.

Activity

  1. jakirkham commented on Jan 2, 2016

    @jakirkham
    Contributor

    Thanks for raising this @njsmith. I had the feeling this was not being done.

  2. jakirkham commented on Jan 2, 2016

    @jakirkham
    Contributor

    Is there any way to take advantage of herk, as well? For instance, noting that A @ A.H has been passed? Would this not be doable in the complex case as A.H returns a copy?

  3. njsmith commented on Jan 2, 2016

    @njsmith
    MemberAuthor

    Right, A.H returns a copy, so there's no way to detect it. There's a
    wacky idea that we could add a transposed-complex dtype that stores x+yi as
    the tuple (x, -y) with appropriate casting functions, and then it would be
    possible for .H to return a view and dot to detect this view. But this
    would be a pretty complicated and intrusive change, and it's far from clear
    that it would be a good idea on net.
    On Jan 2, 2016 9:26 AM, "jakirkham" [email protected] wrote:

    Is there any way to take advantage of herk, as well? For instance, noting
    that A @ A.H has been passed? Would this not be doable in the complex
    case as A.H returns a copy?

    —
    Reply to this email directly or view it on GitHub
    #6794 (comment).

  4. jakirkham commented on Jan 2, 2016

    @jakirkham
    Contributor

    This is a bit of a sidebar, but would it be worth adding an operation that explicitly handles this case. For instance, pdot could represent a pairwise dot product that always takes a single array and multiplies that array by its complex transpose. Other options could be added to disable things like taking the conjugate or change the order of multiplication. A similar extension could be added for tensordot as tensorpdot. Do you have any thoughts on this?

  5. njsmith commented on Jan 2, 2016

    @njsmith
    MemberAuthor

    I don't have an opinion personally b/c I happen not to actually use complex
    numbers in my work, so I can't really assess how important it is :-).
    (Though I guess the fact that no-one bothered to add it in the last 15
    years might suggest something.) A better place for such ideas is the
    numpy-discussion mailing list, which gets a broader audience and is more
    likely to reach the people with relevant experience.

    On Sat, Jan 2, 2016 at 2:57 PM, jakirkham [email protected] wrote:

    This is a bit of a sidebar, but would it be worth adding an operation that
    explicitly handles this case. For instance, pdot could represent a
    pairwise dot product that always takes a single array and multiplies that
    array by its complex transpose. Other options could be added to disable
    things like taking the conjugate or change the order of multiplication. A
    similar extension could be added for tensordot as tensorpdot. Do you have
    any thoughts on this?

    —
    Reply to this email directly or view it on GitHub
    #6794 (comment).

    Nathaniel J. Smith -- http://vorpus.org

  6. charris commented on Jan 2, 2016

    @charris
    Member

    @njsmith I think it would be quite handy. And there is the perennial desire for a *.H method, which would probably be handy even if it returns a transposed, conjugated copy.

  7. jakirkham commented on Jan 2, 2016

    @jakirkham
    Contributor

    The reason I mention this is the transpose documentation states "a view is returned whenever possible".1 It would be nice if this doesn't turn out to be an optimization that is only applied when the memory is shared, but when it is mathematically possible, which may just be easier to have the user decide. I worry that in the former case that it can be challenging to determine whether NumPy is doing the correct thing; whereas, the latter it is clear what should be happening under the hood.

    The complex portion is a bit of a finer detail.

  8. njsmith commented on Jan 3, 2016

    @njsmith
    MemberAuthor

    Possibly the right way to do this would be to add a kwarg flag to dot that says whether the second argument should be conjugated before doting. Then we could internally dispatch to either the efficient A @ B.conj() routine or the efficient A @ A.H routine automatically.

  9. njsmith commented on Jan 3, 2016

    @njsmith
    MemberAuthor

    Anyway, that's just an idea, if someone stumbles across this issue later and is thinking of contributing, then please don't think that adding some special conjugation magic is mandatory before we can start optimizing the simple A @ A.T case :-)

  10. jakirkham commented on Jan 3, 2016

    @jakirkham
    Contributor

    I think I will give it a try for the non-complex case optimization. Maybe the complex case can be done in a second go.

  11. jakirkham commented on Jan 4, 2016

    @jakirkham
    Contributor

    Should this be added for inner, as well? It seems like it can benefit from the same optimization.

  12. jakirkham commented on Jan 4, 2016

    @jakirkham
    Contributor

    So, I think I have a solution for the non-conjugated transposed dot product. If anybody could give me some feedback and maybe try it out, that would be great.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions