Re: [algogeeks] matrix Multiplication

[mike anastasakis]

I need to multiply an array A by it self. Is there an algorithm that does
array multiplication with complexity O(n^2)?Doesn't it take at least O(n^3)?

On Sun, Jan 20, 2013 at 12:44 AM, Dave dave_and_da...@juno.com wrote:

 @Guneesh: I think you mean to say that the complexity of both the
 iterative and recursive algorithms is O(n^3 log k), using the notation of
 the original poster (A is n-by-n, and it is to be raised to the power k).

 If what you really need is a way to calculate A^k * x, for some vector x,
 it may be cheaper to use matrix-vector multiplication k times; this will be
 O(n^2 * k).

 Dave

 On Saturday, January 19, 2013 7:30:50 AM UTC-6, Guneesh wrote:

 both recursive and iterative codes are O(nlogn) algos..
 but memory will be more in recursion..
 so we will prefer iteration

  --




-- 

Re: [algogeeks] matrix Multiplication

[Dave]

@Koup: No, I meant O(n^3 log k). Sorry.
 
Dave

On Sunday, January 20, 2013 3:09:00 AM UTC-6, Koup wrote:

 I need to multiply an array A by it self. Is there an algorithm that does 
 array multiplication with complexity O(n^2)?Doesn't it take at least O(n^3)?

 On Sun, Jan 20, 2013 at 12:44 AM, Dave dave_an...@juno.com 
 javascript:wrote:

 @Guneesh: I think you mean to say that the complexity of both the 
 iterative and recursive algorithms is O(n^3 log k), using the notation of 
 the original poster (A is n-by-n, and it is to be raised to the power k).
  
 If what you really need is a way to calculate A^k * x, for some vector x, 
 it may be cheaper to use matrix-vector multiplication k times; this will be 
 O(n^2 * k).
  
 Dave

 On Saturday, January 19, 2013 7:30:50 AM UTC-6, Guneesh wrote:

 both recursive and iterative codes are O(nlogn) algos..
 but memory will be more in recursion..
 so we will prefer iteration 

  -- 
  
  




-- 

[algogeeks] matrix Multiplication

[Koup]

I want to get the power of an matrix. I mean lets say my matrix is A  i 
wanna get the A ^k. 
I have though the simple algorithm that gives me O(n^3).I though I could do 
some kind of a change to modify it and be faster. I could use the algorithm 
that is used to get the power of a number that checks if the number is even 
or odd and then continue with the calculations but for matrixes..Has anyone 
to suggest something different . 
The language I am writing my code is C. Thank you

-- 

Re: [algogeeks] matrix Multiplication

[Guneesh Paul Singh]

consider code to find n^k where n is an integer

int power()
{
int ans=1,val=1;
while(k)
{
val=val*n;
if(k1)ans=ans*val;
k=k1;
}
return ans;
}

now if n is is a matrix all you have to do is replace * by matrix
multiplication algorithm

-- 

Re: [algogeeks] matrix Multiplication

[Koup]

Just to make sure I understood your code that if means that in case the k 
is an odd number just multiply the accumulator 1 time with the val and 
continue with even k.A question I have is if  a recursive  implementation 
of this would be any faster? 

Τη Σάββατο, 19 Ιανουαρίου 2013 1:06:25 μ.μ. UTC+2, ο χρήστης Guneesh έγραψε:

 consider code to find n^k where n is an integer

 int power()
 {
 int ans=1,val=1;
 while(k)
 {
 val=val*n;
 if(k1)ans=ans*val;
 k=k1;
 }
 return ans;
 }

 now if n is is a matrix all you have to do is replace * by matrix 
 multiplication algorithm


-- 

Re: [algogeeks] matrix Multiplication

[Guneesh Paul Singh]

both recursive and iterative codes are O(nlogn) algos..
but memory will be more in recursion..
so we will prefer iteration

-- 

Re: [algogeeks] matrix Multiplication

[Dave]

@Guneesh: I think you mean to say that the complexity of both the iterative 
and recursive algorithms is O(n^3 log k), using the notation of the 
original poster (A is n-by-n, and it is to be raised to the power k).
 
If what you really need is a way to calculate A^k * x, for some vector x, 
it may be cheaper to use matrix-vector multiplication k times; this will be 
O(n^2 * k).
 
Dave

On Saturday, January 19, 2013 7:30:50 AM UTC-6, Guneesh wrote:

 both recursive and iterative codes are O(nlogn) algos..
 but memory will be more in recursion..
 so we will prefer iteration 

-- 

Re: [algogeeks] matrix Multiplication

[Dave]

@Guneesh: I don't think your code is correct. You want val to take on the 
values n, n^2, n^4, n^8, ..., whereas in your code, val takes on the values 
1,n, n^2, n^3,   The algorithm should be more like this:
 
int power()
{
int ans=1,val=n;
while(k)
{
if(k1)ans=ans*val;
k=k1;
if(k)val=val*val;
}
return ans;
}
 
Dave

On Saturday, January 19, 2013 5:06:25 AM UTC-6, Guneesh wrote:

 consider code to find n^k where n is an integer

 int power()
 {
 int ans=1,val=1;
 while(k)
 {
 val=val*n;
 if(k1)ans=ans*val;
 k=k1;
 }
 return ans;
 }

 now if n is is a matrix all you have to do is replace * by matrix 
 multiplication algorithm


-- 

Re: [algogeeks] matrix Multiplication

[Guneesh Paul Singh]

@dave thanks for correcting :)

--