linogram_fft_test.c

Go to the documentation of this file.

/*
 * Copyright (c) 2002, 2017 Jens Keiner, Stefan Kunis, Daniel Potts
 *
 * This program is free software; you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation; either version 2 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program; if not, write to the Free Software Foundation, Inc., 51
 * Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 */
 
#include <math.h>
#include <stdlib.h>
#include <complex.h>
 
#define NFFT_PRECISION_DOUBLE
 
#include "nfft3mp.h"
 
NFFT_R GLOBAL_elapsed_time;
 
static int linogram_grid(int T, int rr, NFFT_R *x, NFFT_R *w)
{
  int t, r;
  NFFT_R W = (NFFT_R) T * (((NFFT_R) rr / NFFT_K(2.0)) * ((NFFT_R) rr / NFFT_K(2.0)) + NFFT_K(1.0) / NFFT_K(4.0));
 
  for (t = -T / 2; t < T / 2; t++)
  {
    for (r = -rr / 2; r < rr / 2; r++)
    {
      if (t < 0)
      {
        x[2 * ((t + T / 2) * rr + (r + rr / 2)) + 0] = (NFFT_R) (r) / (NFFT_R)(rr);
        x[2 * ((t + T / 2) * rr + (r + rr / 2)) + 1] = NFFT_K(4.0) * ((NFFT_R)(t) + (NFFT_R)(T) / NFFT_K(4.0)) / (NFFT_R)(T)
            * (NFFT_R)(r) / (NFFT_R)(rr);
      }
      else
      {
        x[2 * ((t + T / 2) * rr + (r + rr / 2)) + 0] = -NFFT_K(4.0) * ((NFFT_R)(t) - (NFFT_R)(T) / NFFT_K(4.0)) / (NFFT_R)(T)
            * (NFFT_R)(r) / (NFFT_R)(rr);
        x[2 * ((t + T / 2) * rr + (r + rr / 2)) + 1] = (NFFT_R) r / (NFFT_R)(rr);
      }
      if (r == 0)
        w[(t + T / 2) * rr + (r + rr / 2)] = NFFT_K(1.0) / NFFT_K(4.0) / W;
      else
        w[(t + T / 2) * rr + (r + rr / 2)] = NFFT_M(fabs)((NFFT_R) r) / W;
    }
  }
 
  return T * rr; 
}
 
static int linogram_dft(NFFT_C *f_hat, int NN, NFFT_C *f, int T, int rr, int m)
{
  double t0, t1;
  int j, k; 
  NFFT(plan) my_nfft_plan; 
  NFFT_R *x, *w; 
  int N[2], n[2];
  int M = T * rr; 
  N[0] = NN;
  n[0] = 2 * N[0]; 
  N[1] = NN;
  n[1] = 2 * N[1]; 
  x = (NFFT_R *) NFFT(malloc)((size_t)(2 * T * rr) * (sizeof(NFFT_R)));
  if (x == NULL)
    return EXIT_FAILURE;
 
  w = (NFFT_R *) NFFT(malloc)((size_t)(T * rr) * (sizeof(NFFT_R)));
  if (w == NULL)
    return EXIT_FAILURE;
 
  NFFT(init_guru)(&my_nfft_plan, 2, N, M, n, m,
      PRE_PHI_HUT | PRE_PSI | MALLOC_X | MALLOC_F_HAT | MALLOC_F | FFTW_INIT,
      FFTW_MEASURE);
 
  linogram_grid(T, rr, x, w);
  for (j = 0; j < my_nfft_plan.M_total; j++)
  {
    my_nfft_plan.x[2 * j + 0] = x[2 * j + 0];
    my_nfft_plan.x[2 * j + 1] = x[2 * j + 1];
  }
 
  for (k = 0; k < my_nfft_plan.N_total; k++)
    my_nfft_plan.f_hat[k] = f_hat[k];
 
  t0 = NFFT(clock_gettime_seconds)();
  NFFT(trafo_direct)(&my_nfft_plan);
  t1 = NFFT(clock_gettime_seconds)();
  GLOBAL_elapsed_time = (t1 - t0);
 
  for (j = 0; j < my_nfft_plan.M_total; j++)
    f[j] = my_nfft_plan.f[j];
 
  NFFT(finalize)(&my_nfft_plan);
  NFFT(free)(x);
  NFFT(free)(w);
 
  return EXIT_SUCCESS;
}
 
static int linogram_fft(NFFT_C *f_hat, int NN, NFFT_C *f, int T, int rr, int m)
{
  double t0, t1;
  int j, k; 
  NFFT(plan) my_nfft_plan; 
  NFFT_R *x, *w; 
  int N[2], n[2];
  int M = T * rr; 
  N[0] = NN;
  n[0] = 2 * N[0]; 
  N[1] = NN;
  n[1] = 2 * N[1]; 
  x = (NFFT_R *) NFFT(malloc)((size_t)(2 * T * rr) * (sizeof(NFFT_R)));
  if (x == NULL)
    return EXIT_FAILURE;
 
  w = (NFFT_R *) NFFT(malloc)((size_t)(T * rr) * (sizeof(NFFT_R)));
  if (w == NULL)
    return EXIT_FAILURE;
 
  NFFT(init_guru)(&my_nfft_plan, 2, N, M, n, m,
      PRE_PHI_HUT | PRE_PSI | MALLOC_X | MALLOC_F_HAT | MALLOC_F | FFTW_INIT
          | FFT_OUT_OF_PLACE,
      FFTW_MEASURE | FFTW_DESTROY_INPUT);
 
  linogram_grid(T, rr, x, w);
  for (j = 0; j < my_nfft_plan.M_total; j++)
  {
    my_nfft_plan.x[2 * j + 0] = x[2 * j + 0];
    my_nfft_plan.x[2 * j + 1] = x[2 * j + 1];
  }
 
  if (my_nfft_plan.flags & PRE_LIN_PSI)
    NFFT(precompute_lin_psi)(&my_nfft_plan);
 
  if (my_nfft_plan.flags & PRE_PSI)
    NFFT(precompute_psi)(&my_nfft_plan);
 
  if (my_nfft_plan.flags & PRE_FULL_PSI)
    NFFT(precompute_full_psi)(&my_nfft_plan);
 
  for (k = 0; k < my_nfft_plan.N_total; k++)
    my_nfft_plan.f_hat[k] = f_hat[k];
 
  t0 = NFFT(clock_gettime_seconds)();
  NFFT(trafo)(&my_nfft_plan);
  t1 = NFFT(clock_gettime_seconds)();
  GLOBAL_elapsed_time = (t1 - t0);
 
  for (j = 0; j < my_nfft_plan.M_total; j++)
    f[j] = my_nfft_plan.f[j];
 
  NFFT(finalize)(&my_nfft_plan);
  NFFT(free)(x);
  NFFT(free)(w);
 
  return EXIT_SUCCESS;
}
 
static int inverse_linogram_fft(NFFT_C *f, int T, int rr, NFFT_C *f_hat, int NN,
    int max_i, int m)
{
  double t0, t1;
  int j, k; 
  NFFT(plan) my_nfft_plan; 
  SOLVER(plan_complex) my_infft_plan; 
  NFFT_R *x, *w; 
  int l; 
  int N[2], n[2];
  int M = T * rr; 
  N[0] = NN;
  n[0] = 2 * N[0]; 
  N[1] = NN;
  n[1] = 2 * N[1]; 
  x = (NFFT_R *) NFFT(malloc)((size_t)(2 * T * rr) * (sizeof(NFFT_R)));
  if (x == NULL)
    return EXIT_FAILURE;
 
  w = (NFFT_R *) NFFT(malloc)((size_t)(T * rr) * (sizeof(NFFT_R)));
  if (w == NULL)
    return EXIT_FAILURE;
 
  NFFT(init_guru)(&my_nfft_plan, 2, N, M, n, m,
      PRE_PHI_HUT | PRE_PSI | MALLOC_X | MALLOC_F_HAT | MALLOC_F | FFTW_INIT
          | FFT_OUT_OF_PLACE,
      FFTW_MEASURE | FFTW_DESTROY_INPUT);
 
  SOLVER(init_advanced_complex)(&my_infft_plan,
      (NFFT(mv_plan_complex)*) (&my_nfft_plan), CGNR | PRECOMPUTE_WEIGHT);
 
  linogram_grid(T, rr, x, w);
  for (j = 0; j < my_nfft_plan.M_total; j++)
  {
    my_nfft_plan.x[2 * j + 0] = x[2 * j + 0];
    my_nfft_plan.x[2 * j + 1] = x[2 * j + 1];
    my_infft_plan.y[j] = f[j];
    my_infft_plan.w[j] = w[j];
  }
 
  if (my_nfft_plan.flags & PRE_LIN_PSI)
    NFFT(precompute_lin_psi)(&my_nfft_plan);
 
  if (my_nfft_plan.flags & PRE_PSI)
    NFFT(precompute_psi)(&my_nfft_plan);
 
  if (my_nfft_plan.flags & PRE_FULL_PSI)
    NFFT(precompute_full_psi)(&my_nfft_plan);
 
  if (my_infft_plan.flags & PRECOMPUTE_DAMP)
    for (j = 0; j < my_nfft_plan.N[0]; j++)
      for (k = 0; k < my_nfft_plan.N[1]; k++)
      {
        my_infft_plan.w_hat[j * my_nfft_plan.N[1] + k] = (
            NFFT_M(sqrt)(
                NFFT_M(pow)((NFFT_R)(j - my_nfft_plan.N[0] / 2), NFFT_K(2.0))
                    + NFFT_M(pow)((NFFT_R)(k - my_nfft_plan.N[1] / 2), NFFT_K(2.0)))
                > (NFFT_R)(my_nfft_plan.N[0] / 2) ? 0 : 1);
      }
 
  for (k = 0; k < my_nfft_plan.N_total; k++)
    my_infft_plan.f_hat_iter[k] = NFFT_K(0.0) + _Complex_I * NFFT_K(0.0);
 
  t0 = NFFT(clock_gettime_seconds)();
  SOLVER(before_loop_complex)(&my_infft_plan);
 
  if (max_i < 1)
  {
    l = 1;
    for (k = 0; k < my_nfft_plan.N_total; k++)
      my_infft_plan.f_hat_iter[k] = my_infft_plan.p_hat_iter[k];
  }
  else
  {
    for (l = 1; l <= max_i; l++)
    {
      SOLVER(loop_one_step_complex)(&my_infft_plan);
    }
  }
 
  t1 = NFFT(clock_gettime_seconds)();
  GLOBAL_elapsed_time = (t1 - t0);
 
  for (k = 0; k < my_nfft_plan.N_total; k++)
    f_hat[k] = my_infft_plan.f_hat_iter[k];
 
  SOLVER(finalize_complex)(&my_infft_plan);
  NFFT(finalize)(&my_nfft_plan);
  NFFT(free)(x);
  NFFT(free)(w);
 
  return EXIT_SUCCESS;
}
 
static int comparison_fft(FILE *fp, int N, int T, int rr)
{
  double t0, t1;
  FFTW(plan) my_fftw_plan;
  NFFT_C *f_hat, *f;
  int m, k;
  NFFT_R t_fft, t_dft_linogram;
 
  f_hat = (NFFT_C *) NFFT(malloc)(sizeof(NFFT_C) * (size_t)(N * N));
  f = (NFFT_C *) NFFT(malloc)(sizeof(NFFT_C) * (size_t)((T * rr / 4) * 5));
 
  my_fftw_plan = FFTW(plan_dft_2d)(N, N, f_hat, f, FFTW_BACKWARD, FFTW_MEASURE);
 
  for (k = 0; k < N * N; k++)
    f_hat[k] = NFFT(drand48)() + _Complex_I * NFFT(drand48)();
 
  t0 = NFFT(clock_gettime_seconds)();
  for (m = 0; m < 65536 / N; m++)
  {
    FFTW(execute)(my_fftw_plan);
    /* touch */
    f_hat[2] = NFFT_K(2.0) * f_hat[0];
  }
  t1 = NFFT(clock_gettime_seconds)();
  GLOBAL_elapsed_time = (t1 - t0);
  t_fft = (NFFT_R)(N) * GLOBAL_elapsed_time / NFFT_K(65536.0);
 
  if (N < 256)
  {
    linogram_dft(f_hat, N, f, T, rr, m);
    t_dft_linogram = GLOBAL_elapsed_time;
  }
 
  for (m = 3; m <= 9; m += 3)
  {
    if ((m == 3) && (N < 256))
      fprintf(fp, "%d\t&\t&\t%1.1" NFFT__FES__ "&\t%1.1" NFFT__FES__ "&\t%d\t", N, t_fft, t_dft_linogram,
          m);
    else if (m == 3)
      fprintf(fp, "%d\t&\t&\t%1.1" NFFT__FES__ "&\t       &\t%d\t", N, t_fft, m);
    else
      fprintf(fp, "  \t&\t&\t       &\t       &\t%d\t", m);
 
    printf("N=%d\tt_fft=%1.1" NFFT__FES__ "\tt_dft_linogram=%1.1" NFFT__FES__ "\tm=%d\t", N, t_fft,
        t_dft_linogram, m);
 
    linogram_fft(f_hat, N, f, T, rr, m);
    fprintf(fp, "%1.1" NFFT__FES__ "&\t", GLOBAL_elapsed_time);
    printf("t_linogram=%1.1" NFFT__FES__ "\t", GLOBAL_elapsed_time);
    inverse_linogram_fft(f, T, rr, f_hat, N, m + 3, m);
    if (m == 9)
      fprintf(fp, "%1.1" NFFT__FES__ "\\\\\\hline\n", GLOBAL_elapsed_time);
    else
      fprintf(fp, "%1.1" NFFT__FES__ "\\\\\n", GLOBAL_elapsed_time);
    printf("t_ilinogram=%1.1" NFFT__FES__ "\n", GLOBAL_elapsed_time);
  }
 
  fflush(fp);
 
  NFFT(free)(f);
  NFFT(free)(f_hat);
 
  return EXIT_SUCCESS;
}
 
int main(int argc, char **argv)
{
  int N; 
  int T, rr; 
  int M; 
  NFFT_R *x, *w; 
  NFFT_C *f_hat, *f, *f_direct, *f_tilde;
  int k;
  int max_i; 
  int m;
  NFFT_R temp1, temp2, E_max = NFFT_K(0.0);
  FILE *fp1, *fp2;
  char filename[30];
  int logN;
 
  if (argc != 4)
  {
    printf("linogram_fft_test N T R \n");
    printf("\n");
    printf("N          linogram FFT of size NxN    \n");
    printf("T          number of slopes          \n");
    printf("R          number of offsets         \n");
 
    printf("\nHence, comparison FFTW, linogram FFT and inverse linogram FFT\n");
    fp1 = fopen("linogram_comparison_fft.dat", "w");
    if (fp1 == NULL)
      return (-1);
    for (logN = 4; logN <= 8; logN++)
      comparison_fft(fp1, (int)(1U << logN), 3 * (int)(1U << logN),
          3 * (int)(1U << (logN - 1)));
    fclose(fp1);
 
    return EXIT_FAILURE;
  }
 
  N = atoi(argv[1]);
  T = atoi(argv[2]);
  rr = atoi(argv[3]);
  printf("N=%d, linogram grid with T=%d, R=%d => ", N, T, rr);
 
  x = (NFFT_R *) NFFT(malloc)((size_t)(5 * T * rr / 2) * (sizeof(NFFT_R)));
  w = (NFFT_R *) NFFT(malloc)((size_t)(5 * T * rr / 4) * (sizeof(NFFT_R)));
 
  f_hat = (NFFT_C *) NFFT(malloc)(sizeof(NFFT_C) * (size_t)(N * N));
  f = (NFFT_C *) NFFT(malloc)(sizeof(NFFT_C) * (size_t)(5 * T * rr / 4)); /* 4/pi*log(1+sqrt(2)) = 1.122... < 1.25 */
  f_direct = (NFFT_C *) NFFT(malloc)(sizeof(NFFT_C) * (size_t)(5 * T * rr / 4));
  f_tilde = (NFFT_C *) NFFT(malloc)(sizeof(NFFT_C) * (size_t)(N * N));
 
  M = linogram_grid(T, rr, x, w);
  printf("M=%d.\n", M);
 
  fp1 = fopen("input_data_r.dat", "r");
  fp2 = fopen("input_data_i.dat", "r");
  if ((fp1 == NULL) || (fp2 == NULL))
    return EXIT_FAILURE;
  for (k = 0; k < N * N; k++)
  {
    fscanf(fp1, NFFT__FR__ " ", &temp1);
    fscanf(fp2, NFFT__FR__ " ", &temp2);
    f_hat[k] = temp1 + _Complex_I * temp2;
  }
  fclose(fp1);
  fclose(fp2);
 
  linogram_dft(f_hat, N, f_direct, T, rr, 1);
  //  linogram_fft(f_hat,N,f_direct,T,R,12);
 
  printf("\nTest of the linogram FFT: \n");
  fp1 = fopen("linogram_fft_error.dat", "w+");
  for (m = 1; m <= 12; m++)
  {
    linogram_fft(f_hat, N, f, T, rr, m);
 
    E_max = NFFT(error_l_infty_complex)(f_direct, f, M);
    //E_max=NFFT(error_l_2_complex)(f_direct,f,M);
 
    printf("m=%2d: E_max = %" NFFT__FES__ "\n", m, E_max);
    fprintf(fp1, "%" NFFT__FES__ "\n", E_max);
  }
  fclose(fp1);
 
  for (m = 3; m <= 9; m += 3)
  {
    printf("\nTest of the inverse linogram FFT for m=%d: \n", m);
    sprintf(filename, "linogram_ifft_error%d.dat", m);
    fp1 = fopen(filename, "w+");
    for (max_i = 0; max_i <= 20; max_i += 2)
    {
      inverse_linogram_fft(f_direct, T, rr, f_tilde, N, max_i, m);
 
      E_max = NFFT(error_l_infty_complex)(f_hat, f_tilde, N * N);
      printf("%3d iterations: E_max = %" NFFT__FES__ "\n", max_i, E_max);
      fprintf(fp1, "%" NFFT__FES__ "\n", E_max);
    }
    fclose(fp1);
  }
 
  NFFT(free)(x);
  NFFT(free)(w);
  NFFT(free)(f_hat);
  NFFT(free)(f);
  NFFT(free)(f_direct);
  NFFT(free)(f_tilde);
 
  return EXIT_SUCCESS;
}
/* \} */