Next: Window functions
Up: NFFT
Previous: The case
In summary, the following Algorithm 1 is obtained for the fast computation of
(2.2) with
arithmetic operations.
Algorithm 1 reads in matrix vector notation as
where
denotes the real
sparse matrix
![$\displaystyle \mbox{\boldmath {${B}$}}$](img177.png) ![$\displaystyle := \left( \tilde\psi\left(\mbox{\boldmath {${x}$}}_j - \mbox{\bol...
...1;\, \mbox{\boldmath\scriptsize {${l}$}}\in I_{\mbox{\boldmath\tiny {${n}$}}}},$](img182.png) |
(2.12) |
where
is the Fourier matrix of size
,
and where
is the real
'diagonal' matrix
with zero matrices
![$ {O}$](img188.png)
of size
.
The corresponding computation of the adjoint matrix vector product reads as
With the help of the transposed index set
one obtains Algorithm 2 for the adjoint nfft.
Due to the characterisation of the non zero elements of the matrix
, i.e.,
the multiplication with the sparse matrix
![$ {B}$](img180.png)
is implemented in a 'transposed' way in the library,
summation as outer loop and only using the multi index sets
.
Next: Window functions
Up: NFFT
Previous: The case
Stefan Kunis
2004-09-03