NAG Library Function Document

nag_fft_multiple_qtr_sine (c06hcc)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

+− 10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

1 Purpose

nag_fft_multiple_qtr_sine (c06hcc) computes the discrete quarter-wave Fourier sine transforms of

m

sequences of real data values.

2 Specification

#include <nag.h>

#include <nagc06.h>

void	nag_fft_multiple_qtr_sine (Nag_TransformDirection direct, Integer m, Integer n, double x[], const double trig[], NagError *fail)

3 Description

Given

m

sequences of

n

real data values

x_{j}^{p}

, for

j = 1, 2, \dots, n

and

p = 1, 2, \dots, m

, this function simultaneously calculates the quarter-wave Fourier sine transforms of all the sequences defined by

{\hat{x}}_{k}^{p} = \frac{1}{\sqrt{n}} \{\sum_{j = 1}^{n - 1} x_{j}^{p} \sin (j (2 k - 1) \frac{π}{2 n}) + \frac{1}{2} {(- 1)}^{k - 1} x_{n}^{p}\} if ​ direct,

or its inverse

x_{k}^{p} = \frac{2}{\sqrt{n}} \sum_{j = 1}^{n} {\hat{x}}_{j}^{p} \sin ((2 j - 1) k \frac{π}{2 n}) if ​ direct,

for

k = 1, 2, \dots, n

and

p = 1, 2, \dots, m

(Note the scale factor

\frac{1}{\sqrt{n}}

in this definition.)

A call of the function with

direct = Nag_ForwardTransform

followed by a call with

direct = Nag_BackwardTransform

will restore the original data (but see Section 9).

The transform calculated by this function can be used to solve Poisson's equation when the solution is specified at the left boundary, and the derivative of the solution is specified at the right boundary (Swarztrauber (1977)).

The function uses a variant of the fast Fourier transform (FFT) algorithm (Brigham (1974)) known as the Stockham self-sorting algorithm, described in Temperton (1983), together with pre- and post-processing stages described in Swarztrauber (1982). Special coding is provided for the factors 2, 3, 4, 5 and 6.

4 References

Brigham E O (1974) The Fast Fourier Transform Prentice–Hall

Swarztrauber P N (1977) The methods of cyclic reduction, Fourier analysis and the FACR algorithm for the discrete solution of Poisson's equation on a rectangle SIAM Rev. 19(3) 490–501

Swarztrauber P N (1982) Vectorizing the FFT's Parallel Computation (ed G Rodrique) 51–83 Academic Press

Temperton C (1983) Fast mixed-radix real Fourier transforms J. Comput. Phys. 52 340–350

5 Arguments

1: direct – Nag_TransformDirectionInput

On entry: if the forward transform as defined in Section 3 is to be computed, then direct must be set equal to

Nag_ForwardTransform

. If the backward transform is to be computed, that is the inverse, then direct must be set equal to

Nag_BackwardTransform

Constraint:

direct = Nag_ForwardTransform

Nag_BackwardTransform

2: m – IntegerInput

On entry: the number of sequences to be transformed,

m

Constraint:

m \geq 1

3: n – IntegerInput

On entry: the number of real values in each sequence,

n

Constraint:

n \geq 1

4: x[ $m \times n$ ] – doubleInput/Output

On entry: the

m

data sequences stored in x consecutively. If the data values of the

p

th sequence to be transformed are denoted by

x_{j}^{p}

, for

j = 1, 2, \dots, n

and

p = 1, 2, \dots, m

, then the first

m n

elements of the array x must contain the values

x_{1}^{1}, x_{2}^{1}, \dots, x_{n}^{1}, x_{1}^{2}, x_{2}^{2}, \dots, x_{n}^{2}, \dots, x_{1}^{m}, x_{2}^{m}, \dots, x_{n}^{m} .

On exit: the

m

quarter-wave sine transforms stored consecutively.

5: trig[ $2 \times n$ ] – const doubleInput

On entry: trigonometric coefficients as returned by a call of nag_fft_init_trig (c06gzc). nag_fft_multiple_qtr_sine (c06hcc) makes a simple check to ensure that trig has been initialized and that the initialization is compatible with the value of n.

6: fail – NagError *Input/Output

The NAG error argument (see Section 3.6 in the Essential Introduction).

6 Error Indicators and Warnings

NE_ALLOC_FAIL: Dynamic memory allocation failed.
NE_BAD_PARAM: On entry, argument direct had an illegal value.
NE_C06_NOT_TRIG: Value of n and trig array are incompatible or trig array not initialized.
NE_INT_ARG_LT: On entry, $m = ⟨value⟩$ .
Constraint: $m \geq 1$ .
On entry, $n = ⟨value⟩$ .
Constraint: $n \geq 1$ .

7 Accuracy

Some indication of accuracy can be obtained by performing a subsequent inverse transform and comparing the results with the original sequence (in exact arithmetic they would be identical).

8 Parallelism and Performance

Not applicable.

9 Further Comments

The time taken is approximately proportional to

n m \log (n)

, but also depends on the factors of

n

. The function is fastest if the only prime factors of

n

are 2, 3 and 5, and is particularly slow if

n

is a large prime, or has large prime factors.

10 Example

This program reads in sequences of real data values and prints their quarter-wave sine transforms as computed by nag_fft_multiple_qtr_sine (c06hcc) with

direct = Nag_ForwardTransform

. It then calls nag_fft_multiple_qtr_sine (c06hcc) again with

direct = Nag_BackwardTransform

and prints the results which may be compared with the original data.

NAG Library Function Documentnag_fft_multiple_qtr_sine (c06hcc)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

NAG Library Function Document

nag_fft_multiple_qtr_sine (c06hcc)