Time comparison between Fast Fourier Transform and MultApproxFewRecombonation

         Running Environment :    Windows XP pro, P4 3.2, 512 MB RAM

The table shows the runtime in milliseconds when performing one vector matrix multiplication with size = 2N

N

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

Fast Fourier Transform (Fft)

0

0

0

15

0

15

16

47

141

313

672

1406

2984

6219

19421

multApproxOneRecombination

0

0

0

0

0

16

16

15

47

94

234

469

1078

2157

8141

multApproxFewRecombinations (MAX_ALLOWED_RECOMBINATIONS = 2)

0

15

0

16

16

31

94

219

812

2141

6157

15859

37703

64421

131563

multApproxFewRecombinations (MAX_ALLOWED_RECOMBINATIONS = 3)

0

0

31

78

188

469

1156

2843

13500

37047

105375

279610

698578

1499969

3678343

 

Conclusions:

Ø      The above table and the following chart point that the approximation method is only beneficial when no more then one recombination is probable between consecutive markers this is also shown in the time complexity calculation.

 

A closer look at multApproxOneRecombination:

N

17

18

19

20

21

22

23

24

Fast Fourier Transform (Fft)

47

141

313

672

1406

2984

6219

19421

multApproxOneRecombination

15

47

94

234

469

1078

2157

8141

runtime ratio FFT/MultApproxOne

3.133333

3

3.329787

2.871795

2.997868

2.768089

2.883171

2.385579

 

Conclusions:

Ø      The above chart shows that multApproxOneRecombination performs about three times better then the Fast Fourier Transform approach without additional memory use.

 

back to main