The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
rt servo

Posts: 19
Registered: 2/1/05
Re: sum of matrices
Posted: Oct 8, 2012 1:29 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On 08/10/2012 1:26 PM, Rupert wrote:
> On Oct 8, 6:17 pm, Kiuhnm <> wrote:
>> On 10/8/2012 16:45, Rupert wrote:

>>> On Oct 8, 4:18 pm, Kiuhnm <> 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.

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.