3d Tensor multiplication -> 3D x 3D = 2D

[Ste]

Hello,

I am looking for some elegant solution/function that does automated/fast tensor multiplication

3D_Matrix_1[s,k,p] x 3D_Matrix_2[p, g, k] = 2D_Matrix_3[g,s];

I can do it with some for() loop, but would be great if there was a function that speed this calculation up.

Thanks a lot.

[Bob Carpenter]

We don't have any tensor multiplication built in, so you'll
have to break it down into components.

Best if those are themselves matrix multiplies if possible, so the
trick's setting up the tensors to support efficient indexing. There's
a chapter in the manual on arrays vs. vectors that should help.

Overall, that loop's not going to be a big deal in terms of
efficiency, but big tensor multiplies get expensive quickly (even
multiply N x N matrices is an N^3 operation).

- Bob

> --
> You received this message because you are subscribed to the Google Groups "Stan users mailing list" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+...@googlegroups.com.
> To post to this group, send email to stan-...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[stefano]

Thanks,

I don't know if it possible at all, but I spent some time to see if a formulation was possible to convert 3D tensor multiplication in a combination of 2D matrices, but so far the answer is not. It might be that 3D and 2D are not linked by grouping property.

A built-in function would be amazing though, that would do:

- 2D * 3D

- 3D * 3D

multiplications, they would save an a lot of inefficient code.

Bw

2017-04-27 3:45 GMT+10:00 Bob Carpenter <ca...@alias-i.com>:

We don't have any tensor multiplication built in, so you'll
have to break it down into components.

Best if those are themselves matrix multiplies if possible, so the
trick's setting up the tensors to support efficient indexing.  There's
a chapter in the manual on arrays vs. vectors that should help.

Overall, that loop's not going to be a big deal in terms of
efficiency, but big tensor multiplies get expensive quickly (even
multiply N x N matrices is an N^3 operation).

- Bob

> On Apr 26, 2017, at 2:58 AM, Ste <mangiol...@gmail.com> wrote:
>
> Hello,
>
> I am looking for some elegant solution/function that does automated/fast tensor multiplication
>
> 3D_Matrix_1[s,k,p] x 3D_Matrix_2[p, g, k] = 2D_Matrix_3[g,s];
>
> I can do it with some for() loop, but would be great if there was a function that speed this calculation up.
>
> Thanks a lot.
>
> --
> You received this message because you are subscribed to the Google Groups "Stan users mailing list" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+unsubscribe@googlegroups.com.

> To post to this group, send email to stan-...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to a topic in the Google Groups "Stan users mailing list" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/stan-users/76YG_zOXat8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to stan-users+unsubscribe@googlegroups.com.

[Daniel Lee]

Hi Stephano,

I'm not really sure what you mean. I looked at the original post and I'm not following. Can you write a Stan function to compute it? Maybe that would help. 

In Stan, matrices have 2 (and only 2) dimensions. Arrays can have as many dimensions as you want. And you can have arrays of any type. 

Regarding speed, I'd first think about having a working implementation before even considering how fast it goes. 

Daniel

To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+...@googlegroups.com.

[stefano]

Yes at the moment I coded that into a ad-hoc case, a quite non-elegant formulation, I didn't think about writing a generic function that would do such 3/2D multiplication.

But I will have a go, especially if I find my self in the situation to use it in more than one occasion/project.

Thanks.

[Ben B]

So if Einstein summation notation is what you want, and

A_skp * B_pgk -> C_sg

is what you need (multiplying and summing across k and p [I transposed your output also])

Then rearrange the B indices (call it B'):

A_skp * B'_kpg -> C_sg

Flatten the kp indices together into one new index (j) and call things matrices (Am, Bm):

Am_sj * Bm_jg -> C_sg

And that's just regular matrix multiplication I think.

Here's a little python snippet to play with:

import numpy

A = numpy.random.rand(3, 4, 5)
B = numpy.random.rand(4, 5, 3)

print numpy.einsum('ijk, jkl', A, B)

Am = A.reshape(3, 4 * 5)
Bm = B.reshape(4 * 5, 3)

print Am.dot(Bm)

Ben

[Bob Carpenter]

I still don't know what funciton you're asking for because
I don't know anything about tensors.

If you want to express it as an issue in stan-dev/math
with a pointer to a definition, that'd be helpful.

Stan doesn't have a tensor type, but we could add one.
Or you can have an array of matrices holding the same
values.

- Bob

>> > To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+...@googlegroups.com.

>> > To post to this group, send email to stan-...@googlegroups.com.
>> > For more options, visit https://groups.google.com/d/optout.
>>
>> --
>> You received this message because you are subscribed to a topic in the Google Groups "Stan users mailing list" group.
>> To unsubscribe from this topic, visit https://groups.google.com/d/topic/stan-users/76YG_zOXat8/unsubscribe.

>> To unsubscribe from this group and all its topics, send an email to stan-users+...@googlegroups.com.

>> To post to this group, send email to stan-...@googlegroups.com.
>> For more options, visit https://groups.google.com/d/optout.
>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups "Stan users mailing list" group.

>> To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+...@googlegroups.com.

>> To post to this group, send email to stan-...@googlegroups.com.
>> For more options, visit https://groups.google.com/d/optout.
>
> --
> You received this message because you are subscribed to a topic in the Google Groups "Stan users mailing list" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/topic/stan-users/76YG_zOXat8/unsubscribe.

> To unsubscribe from this group and all its topics, send an email to stan-users+...@googlegroups.com.

> To post to this group, send email to stan-...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>
>
> --
> You received this message because you are subscribed to the Google Groups "Stan users mailing list" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+...@googlegroups.com.

[stefano]

Sure Bob,

I will try to be more specific, give the fact that I don't know much about tensor Math as well.

Tensor multiplication is useful when you have problems of deconvolution of regressions (instead of numbers), while a regression is a 2D x 2D , the sum of regressions is a tensor multiplication.

The difference in work needed between (i) using one function that takes N_dimensional tensor and is able to efficiently multiply it by a N_d or (N-1)_d,  or code it your self (in a probably dirty way), is huge.

Getting around the logic of tensor multiplication is a brain puzzle.

Thanks.

>> > To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+unsubscribe@googlegroups.com.

>> > To post to this group, send email to stan-...@googlegroups.com.
>> > For more options, visit https://groups.google.com/d/optout.
>>
>> --
>> You received this message because you are subscribed to a topic in the Google Groups "Stan users mailing list" group.
>> To unsubscribe from this topic, visit https://groups.google.com/d/topic/stan-users/76YG_zOXat8/unsubscribe.

>> To unsubscribe from this group and all its topics, send an email to stan-users+unsubscribe@googlegroups.com.

>> To post to this group, send email to stan-...@googlegroups.com.
>> For more options, visit https://groups.google.com/d/optout.
>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups "Stan users mailing list" group.

>> To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+unsubscribe@googlegroups.com.

>> To post to this group, send email to stan-...@googlegroups.com.
>> For more options, visit https://groups.google.com/d/optout.
>
> --
> You received this message because you are subscribed to a topic in the Google Groups "Stan users mailing list" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/topic/stan-users/76YG_zOXat8/unsubscribe.

> To unsubscribe from this group and all its topics, send an email to stan-users+unsubscribe@googlegroups.com.

> To post to this group, send email to stan-...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>
>
> --
> You received this message because you are subscribed to the Google Groups "Stan users mailing list" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+unsubscribe@googlegroups.com.

> To post to this group, send email to stan-...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to a topic in the Google Groups "Stan users mailing list" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/stan-users/76YG_zOXat8/unsubscribe.

To unsubscribe from this group and all its topics, send an email to stan-users+unsubscribe@googlegroups.com.

[Bob Carpenter]

I don't even see the brain puzzle.

There's probably some standard definition of tensor multiplication
I don't know. The wikipedia page is impenetrable. I may be asking
too simple a question---what are the dimensions of
the inputs, what is the dimension of the output, and how is the
value at each output position defined.

Here's the Eigen page for their tensor data structure:

https://eigen.tuxfamily.org/dox-devel/unsupported/group__CXX11__Tensor__Module.html

- Bob

> >> > To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+...@googlegroups.com.

> >> > To post to this group, send email to stan-...@googlegroups.com.
> >> > For more options, visit https://groups.google.com/d/optout.
> >>
> >> --
> >> You received this message because you are subscribed to a topic in the Google Groups "Stan users mailing list" group.
> >> To unsubscribe from this topic, visit https://groups.google.com/d/topic/stan-users/76YG_zOXat8/unsubscribe.

> >> To unsubscribe from this group and all its topics, send an email to stan-users+...@googlegroups.com.

> >> To post to this group, send email to stan-...@googlegroups.com.
> >> For more options, visit https://groups.google.com/d/optout.
> >>
> >>
> >> --
> >> You received this message because you are subscribed to the Google Groups "Stan users mailing list" group.

> >> To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+...@googlegroups.com.

> >> To post to this group, send email to stan-...@googlegroups.com.
> >> For more options, visit https://groups.google.com/d/optout.
> >
> > --
> > You received this message because you are subscribed to a topic in the Google Groups "Stan users mailing list" group.
> > To unsubscribe from this topic, visit https://groups.google.com/d/topic/stan-users/76YG_zOXat8/unsubscribe.

> > To unsubscribe from this group and all its topics, send an email to stan-users+...@googlegroups.com.

> > To post to this group, send email to stan-...@googlegroups.com.
> > For more options, visit https://groups.google.com/d/optout.
> >
> >
> > --
> > You received this message because you are subscribed to the Google Groups "Stan users mailing list" group.

> > To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+...@googlegroups.com.

> > To post to this group, send email to stan-...@googlegroups.com.
> > For more options, visit https://groups.google.com/d/optout.
>
> --
> You received this message because you are subscribed to a topic in the Google Groups "Stan users mailing list" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/topic/stan-users/76YG_zOXat8/unsubscribe.

> To unsubscribe from this group and all its topics, send an email to stan-users+...@googlegroups.com.

> To post to this group, send email to stan-...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>
>
> --
> You received this message because you are subscribed to the Google Groups "Stan users mailing list" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+...@googlegroups.com.

[Michael Betancourt]

Given a basis a 3D tensor is just a 3D array, so the we can specify
it with the N^{3} elements A_{ijk}. Then the specific operation
implied by the subjectline would be something like

C_{ij} = sum{m, n, o = 1}^{N} A_{imn} B_{jmn}

although you have to be careful about the order if the tensors are
not symmetric.

Without an efficient tensor library in Stan, however, there’s really
nothing to be gained by trying to pack a problem into tensors and
then hack tensor operations as opposed to looping over matrix
operations directly.

[Bob Carpenter]

Thanks---that answers my question. And it reduces the original
question to how to implement this most efficiently in Stan.
I think that's just

matrix[M, N] A[I];
matrix[M, N] B[J];

matrix[I, J] C = tensor_product(A, B);

where we define the function

// C_{ij} = sum{m, n = 1}^{N} A_{imn} B_{jmn}
matrix tensor_product(matrix[] A matrix[] B) {
matrix[size(A), size(B)] C;
for (j in 1:J)
for (i in 1:I)
c[i, j] = sum(A[i] .* B[j]);
return c;
}

I like when these things work out about as neatly as the original
formula (I removed the o variable as it wasn't used).

We could technically write analytic derivatives for sum(matrix .* matrix)
that would be both faster and less memory intensive than what you get
from the above. I turned it into an issue because I think the above
is a pain for a user to have to write if this is a common operation:

https://github.com/stan-dev/math/issues/543

- Bob