Skip to content

Add a function to compute trace of matrix product efficiently #3161

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
jachymb opened this issue Mar 6, 2025 · 0 comments
Open

Add a function to compute trace of matrix product efficiently #3161

jachymb opened this issue Mar 6, 2025 · 0 comments

Comments

@jachymb
Copy link

jachymb commented Mar 6, 2025

I figured something like this could be useful (although not strictly necessary) pre-requisite for #3149

Consider rectangular matrices A R m × n , B R n × m . We can observe the following:

Trace ( A B ) = i A i ( B T ) i = i j A i , j B j , i

The left-hand-side expression is elegant and concise way to write it. From programmers perspective, it's convenient especially when we already have matrices on input.

The middle expression seems like a good way to compute the value in a vectorized way. It's asymptotically faster than computing the whole product and then taking the trace.

The right-hand-side expression is just expanded form and may appear in the wild. It suggests computing it as sum of elementwise product of A and B T which is maybe better computationally, but kinda obscures the linear-algebraic structure.

I thus suggest we add a function like real trace_dot(matrix a, matrix b). Note that we already have functions like trace_quad_form that do something related.

Not sure if the property Trace ( A B ) = Trace ( B A ) can be useful here, but it allows us to choose (in the middle formula) to do either more dot products of shorter vectors or fewer dot-products of longer vectors. It should amount to the same number of multiplications but perhaps for hardware acceleration one of those is preferred.

For autodiff, I think there is

d d A Trace ( A B ) = B T

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant