Content deleted Content added
Line 54:
<math>C_{ij}=\sum_{k=1}^m A_{ik}B_{kj}\,</math>
To compute each element in {{math|'''C'''}} takes {{math|''m''}} multiplications and {{math|(''m'' - ''1'')}} additions. Therefore, with a CPU implementation, the time complexity to achieve this computation is ''Θ(n''<sup href="Category:GPGPU">''3''</sup>'')'' in the following C example''.'' However, we have known that elements in {{math|'''C'''}} are independent to each others. Hence, the computation can be fully parallelized by SIMD processors, such as GPGPU devices. With a GPGPU implementation, the time complexity reduces to ''Θ(n
=== Multidimensional Fast Fourier Transform Transform ===
| |||