Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: sum of matrices
Replies: 17   Last Post: Oct 9, 2012 9:01 AM

 Messages: [ Previous | Next ]
 rt servo Posts: 19 Registered: 2/1/05
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.

Date Subject Author
10/8/12 Kiuhnm
10/8/12 Rupert
10/8/12 Kiuhnm
10/8/12 Rupert
10/8/12 Kiuhnm
10/8/12 Kiuhnm
10/8/12 Rupert
10/8/12 Pubkeybreaker
10/8/12 Rupert
10/8/12 Kiuhnm
10/8/12 Rupert
10/8/12 rt servo
10/8/12 Rupert
10/8/12 Kiuhnm
10/8/12 Pubkeybreaker
10/8/12 gus gassmann
10/8/12 Stephen Montgomery-Smith
10/9/12 Pubkeybreaker