# Question:Can we optimize Matrix-Vector operations with the LinearAlgebra package or is O(n^3) ~ O(n^2)

## Question:Can we optimize Matrix-Vector operations with the LinearAlgebra package or is O(n^3) ~ O(n^2)

Maple

The following example shows some typical computations with Householder- or reflextion matrices. Why are the second and third variants only slightly better than the first one? Could we get a real speedup without rtable/NAG/BLAS/etc. tricks?

\$ maple15
|\^/|     Maple 15 (X86 64 LINUX)
._|\|   |/|_. Copyright (c) Maplesoft, a division of Waterloo Maple Inc. 2011
<____ ____>  Waterloo Maple Inc.
|       Type ? for help.
> restart:
> with(LinearAlgebra):
> N := 10:
> M := 200:
> Times := Matrix(4,N):
> for k from 1 to N do
>   n := k*M:
>   h := RandomVector(n, outputoptions=[datatype=float]):
>   h := (1/DotProduct(h,h))*h:
>   B := RandomMatrix(n, outputoptions=[datatype=float]):
>   Times[1,k] := n:
>   ## 1.try
>   st:= time():
>   B - 2*(h.h^%T).B:  ## O(n^3)?!
>   Times[2,k] := time() - st:
>   ## 2.try
>   st:= time():
>   B - (2*h).(h^%T.B): ## O(n^2)?!
>   Times[3,k] := time() - st:
>   ## 3.try
>   st:= time():
>   hb := Vector[row]([seq( DotProduct(h,B[1..n,j]), j = 1..n )]):
>   B - (2*h).hb:  ## O(n^2)?!
>   Times[4,k] := time() - st:
> end do:
memory used=108.2MB, alloc=106.6MB, time=1.47

.....
memory used=5124.1MB, alloc=958.5MB, time=93.14
> Times;
[ 200      400      600      800     1000     1200     1400     1600     1800      2000 ]
[                                                                                       ]
[0.080    0.288    0.848    1.536    2.419    3.266    4.632    6.429    8.351    10.417]
[                                                                                       ]
[0.055    0.230    0.505    1.156    1.603    2.492    3.471    4.650    5.904    7.164 ]
[                                                                                       ]
[0.073    0.237    0.687    1.005    1.778    2.449    3.830    4.640    5.647    6.899 ]

>

﻿