Usage
=====

All types and functions of the SFFT library are defined in the header
``sfft.h``. Include it at the beginning of your program.


Computing Sparse DFTs
---------------------

Creating Plans
++++++++++++++

SFFT executions consist of two seperate steps: planning and execution. The
planning phase is only executed once for specific input parameters. After
that, many Sparse DFTs with these input parameters can be computed (on
different input vectors). This concept is similar to FFTW's concept of plans.

You can create a plan with a call to ``sfft_plan``::

    sfft_plan* sfft_make_plan(int n, int k, sfft_version version,
                              int fftw_optimization);

The call returns a pointer to a struct of type ``sfft_plan``, which has to be
manually freed with ``sfft_free_plan``. Parameters of ``sfft_make_plan`` are:

``n``
    The size of the input vector.
``k``
    The number of frequencies in the signal, i.e. the signal's *sparsity*.
``version``
    The SFFT algorithm version to use. Either ``SFFT_VERSION_1``,
    ``SFFT_VERSION_2``, or ``SFFT_VERSION_3``.
``fftw_optimization``
    FFTW optimization level. Usually one of ``FFTW_MEASURE`` and 
    ``FFTW_ESTIMATE``. Since experiments showed that there is little benefit 
    in using the more expensive ``FFTW_MEASURE``, the best choice is typically
    ``FFTW_ESTIMATE``.


Creating Input Vectors
++++++++++++++++++++++

The storage for SFFT input vectors has to allocated using ``sfft_malloc``::

    void* sfft_malloc(size_t s);

The reason for this is that the implementation requires a specific memory
alignment on the input vectors. You can use ``sfft_malloc`` as a drop-in
replacement for ``malloc``.

Input vectors should be of type ``complex_t``, which is a typedef to the C
standard library's type ``double complex``.

Storage allocated with ``sfft_malloc`` must be freed with this function::

    void sfft_free(void*);


Creating the Output Datastructure
+++++++++++++++++++++++++++++++++

The output of the SFFT is stored in an associative array that maps frequency
coordinates to coefficients.  The array should be of type ``sfft_output``,
which is a typedef to an ``std::unordered_map``. Before executing the SFFT
plans, you need to create the output datastructure. A pointer to it is passed
to the SFFT execution call and the datastructure filled with the result.


Computing a Single Sparse DFT
+++++++++++++++++++++++++++++

Once a plan is created, input vectors are created filled with data, and an
output object was allocated, the SFFT plans can be executed. The function for
this is::

    void sfft_exec(sfft_plan* plan, complex_t* in, sfft_output* out);

Parameters should be self-explanatory. After execution of this function, the
output of the DFT is stored in ``*out``.


Computing Multiple Sparse DFTs
++++++++++++++++++++++++++++++

If you want to run multiple SFFT calls on different inputs (but with the same
input sizes), you can use ``sfft_exec_many`` to run the calls in parallel::

    void sfft_exec_many(sfft_plan* plan, 
                        int num, complex_t** in, sfft_output* out);

The function is very similar to ``sfft_exec``, but you can pass it put ``num``
input-vectors and ``num`` output-objects. The SFFT library used OpenMP for
parallelization; thus, you can use either the environment variable
``OMP_NUM_THREADS`` or OpenMP library functions to adjust the number of
threads. Be careful: do *not* use different thread number configuration for
the  call to ``sfft_make_plan`` and ``sfft_exec_many``. Otherwise your
program will crash!


SFFT Versions
-------------

Currently, three different SFFT versions are implemented: SFFT v1, v2, and v3.

SFFT v3 is the algorithm of choice when your input signals are exactly-sparse;
that is, there is no additional noise in the signals. SFFT v3 will not work
with noisy signals.


SFFT v1 and v2 can also be applied to noisy signals, but they only work with
certain input parameter combinations. Valid input parameters combinations:

============ ========
Signal Size  Sparsity
============ ========
8192         50
16384        50
32768        50
65536        50
131072       50
262144       50
524288       50
1048576      50
2097152      50
4194304      50
8388608      50
16777216     50
4194304      50
4194304      100
4194304      200
4194304      500
4194304      1000
4194304      2000
4194304      2500
4194304      4000
============ ========