
Re: sum of matrices
Posted:
Oct 8, 2012 1:29 PM


On 08/10/2012 1:26 PM, Rupert wrote: > On Oct 8, 6:17 pm, Kiuhnm <kiuhnm03.4t.yahoo.it> wrote: >> On 10/8/2012 16:45, Rupert wrote: >> >>> On Oct 8, 4:18 pm, Kiuhnm <kiuhnm03.4t.yahoo.it> wrote: >>>> On 10/8/2012 13:35, Kiuhnm wrote: >> >>>>> Let X_1,...,X_m and Y_1,...,Y_m be column vectors of length n. >>>>> I need to compute >>>>> Sum_{i=1}^m X_i^T Y_i >>>>> The trivial algorithm takes time O(m n^2). Can we do better? >> >>>> Sorry. I meant >>>> Sum_{i=1}^m X_i Y_i^T >> >>>> Kiuhnm >> >>> Well, you need to look at mn^2 pieces of data, it would seem, so it's >>> hard to see how you could get around that. >> >> I think I've found a way. >> Let assume that m = n. >> The i,j element of the final matrix is given by >> Sum_{k=1}^n {X_k}_i {Y_k}_j >> But that looks like a sort of dot product, doesn't it? >> So, if X and Y are nxn matrices where X_{i,j} = {X_j}_i and Y_{i,j} = >> {Y_i}_j, then the sum above becomes >> Sum_{k=1}^n X_{i,k} Y_{k,j} >> that is >> [XY]_{i,j} >> So we can solve the problem in O(n^{2+o(1)}) >> Does it make sense?
What in the world do you mean by O(n^{2+o(1)})? Isn't that just O(n^3) as before? If not, explain a bit better how you want to take n^2 dot products with, on average, less than n operations each.

