Mercurial > hg > sv-dependency-builds

annotate src/fftw-3.3.3/doc/html/More-DFTs-of-Real-Data.html @ 83:ae30d91d2ffe

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Replace these with versions built using an older toolset (so as to avoid ABI compatibilities when linking on Ubuntu 14.04 for packaging purposes)
author Chris Cannam
date Fri, 07 Feb 2020 11:51:13 +0000
parents 37bf6b4a2645
children
rev   line source
Chris@10 1 <html lang="en">
Chris@10 2 <head>
Chris@10 3 <title>More DFTs of Real Data - FFTW 3.3.3</title>
Chris@10 4 <meta http-equiv="Content-Type" content="text/html">
Chris@10 5 <meta name="description" content="FFTW 3.3.3">
Chris@10 6 <meta name="generator" content="makeinfo 4.13">
Chris@10 7 <link title="Top" rel="start" href="index.html#Top">
Chris@10 8 <link rel="up" href="Tutorial.html#Tutorial" title="Tutorial">
Chris@10 9 <link rel="prev" href="Multi_002dDimensional-DFTs-of-Real-Data.html#Multi_002dDimensional-DFTs-of-Real-Data" title="Multi-Dimensional DFTs of Real Data">
Chris@10 10 <link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
Chris@10 11 <!--
Chris@10 12 This manual is for FFTW
Chris@10 13 (version 3.3.3, 25 November 2012).
Chris@10 14
Chris@10 15 Copyright (C) 2003 Matteo Frigo.
Chris@10 16
Chris@10 17 Copyright (C) 2003 Massachusetts Institute of Technology.
Chris@10 18
Chris@10 19 Permission is granted to make and distribute verbatim copies of
Chris@10 20 this manual provided the copyright notice and this permission
Chris@10 21 notice are preserved on all copies.
Chris@10 22
Chris@10 23 Permission is granted to copy and distribute modified versions of
Chris@10 24 this manual under the conditions for verbatim copying, provided
Chris@10 25 that the entire resulting derived work is distributed under the
Chris@10 26 terms of a permission notice identical to this one.
Chris@10 27
Chris@10 28 Permission is granted to copy and distribute translations of this
Chris@10 29 manual into another language, under the above conditions for
Chris@10 30 modified versions, except that this permission notice may be
Chris@10 31 stated in a translation approved by the Free Software Foundation.
Chris@10 32 -->
Chris@10 33 <meta http-equiv="Content-Style-Type" content="text/css">
Chris@10 34 <style type="text/css"><!--
Chris@10 35 pre.display { font-family:inherit }
Chris@10 36 pre.format { font-family:inherit }
Chris@10 37 pre.smalldisplay { font-family:inherit; font-size:smaller }
Chris@10 38 pre.smallformat { font-family:inherit; font-size:smaller }
Chris@10 39 pre.smallexample { font-size:smaller }
Chris@10 40 pre.smalllisp { font-size:smaller }
Chris@10 41 span.sc { font-variant:small-caps }
Chris@10 42 span.roman { font-family:serif; font-weight:normal; }
Chris@10 43 span.sansserif { font-family:sans-serif; font-weight:normal; }
Chris@10 44 --></style>
Chris@10 45 </head>
Chris@10 46 <body>
Chris@10 47 <div class="node">
Chris@10 48 <a name="More-DFTs-of-Real-Data"></a>
Chris@10 49 <p>
Chris@10 50 Previous:&nbsp;<a rel="previous" accesskey="p" href="Multi_002dDimensional-DFTs-of-Real-Data.html#Multi_002dDimensional-DFTs-of-Real-Data">Multi-Dimensional DFTs of Real Data</a>,
Chris@10 51 Up:&nbsp;<a rel="up" accesskey="u" href="Tutorial.html#Tutorial">Tutorial</a>
Chris@10 52 <hr>
Chris@10 53 </div>
Chris@10 54
Chris@10 55 <h3 class="section">2.5 More DFTs of Real Data</h3>
Chris@10 56
Chris@10 57 <ul class="menu">
Chris@10 58 <li><a accesskey="1" href="The-Halfcomplex_002dformat-DFT.html#The-Halfcomplex_002dformat-DFT">The Halfcomplex-format DFT</a>
Chris@10 59 <li><a accesskey="2" href="Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029.html#Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029">Real even/odd DFTs (cosine/sine transforms)</a>
Chris@10 60 <li><a accesskey="3" href="The-Discrete-Hartley-Transform.html#The-Discrete-Hartley-Transform">The Discrete Hartley Transform</a>
Chris@10 61 </ul>
Chris@10 62
Chris@10 63 <p>FFTW supports several other transform types via a unified <dfn>r2r</dfn>
Chris@10 64 (real-to-real) interface,
Chris@10 65 <a name="index-r2r-65"></a>so called because it takes a real (<code>double</code>) array and outputs a
Chris@10 66 real array of the same size. These r2r transforms currently fall into
Chris@10 67 three categories: DFTs of real input and complex-Hermitian output in
Chris@10 68 halfcomplex format, DFTs of real input with even/odd symmetry
Chris@10 69 (a.k.a. discrete cosine/sine transforms, DCTs/DSTs), and discrete
Chris@10 70 Hartley transforms (DHTs), all described in more detail by the
Chris@10 71 following sections.
Chris@10 72
Chris@10 73 <p>The r2r transforms follow the by now familiar interface of creating an
Chris@10 74 <code>fftw_plan</code>, executing it with <code>fftw_execute(plan)</code>, and
Chris@10 75 destroying it with <code>fftw_destroy_plan(plan)</code>. Furthermore, all
Chris@10 76 r2r transforms share the same planner interface:
Chris@10 77
Chris@10 78 <pre class="example"> fftw_plan fftw_plan_r2r_1d(int n, double *in, double *out,
Chris@10 79 fftw_r2r_kind kind, unsigned flags);
Chris@10 80 fftw_plan fftw_plan_r2r_2d(int n0, int n1, double *in, double *out,
Chris@10 81 fftw_r2r_kind kind0, fftw_r2r_kind kind1,
Chris@10 82 unsigned flags);
Chris@10 83 fftw_plan fftw_plan_r2r_3d(int n0, int n1, int n2,
Chris@10 84 double *in, double *out,
Chris@10 85 fftw_r2r_kind kind0,
Chris@10 86 fftw_r2r_kind kind1,
Chris@10 87 fftw_r2r_kind kind2,
Chris@10 88 unsigned flags);
Chris@10 89 fftw_plan fftw_plan_r2r(int rank, const int *n, double *in, double *out,
Chris@10 90 const fftw_r2r_kind *kind, unsigned flags);
Chris@10 91 </pre>
Chris@10 92 <p><a name="index-fftw_005fplan_005fr2r_005f1d-66"></a><a name="index-fftw_005fplan_005fr2r_005f2d-67"></a><a name="index-fftw_005fplan_005fr2r_005f3d-68"></a><a name="index-fftw_005fplan_005fr2r-69"></a>
Chris@10 93 Just as for the complex DFT, these plan 1d/2d/3d/multi-dimensional
Chris@10 94 transforms for contiguous arrays in row-major order, transforming (real)
Chris@10 95 input to output of the same size, where <code>n</code> specifies the
Chris@10 96 <em>physical</em> dimensions of the arrays. All positive <code>n</code> are
Chris@10 97 supported (with the exception of <code>n=1</code> for the <code>FFTW_REDFT00</code>
Chris@10 98 kind, noted in the real-even subsection below); products of small
Chris@10 99 factors are most efficient (factorizing <code>n-1</code> and <code>n+1</code> for
Chris@10 100 <code>FFTW_REDFT00</code> and <code>FFTW_RODFT00</code> kinds, described below), but
Chris@10 101 an <i>O</i>(<i>n</i>&nbsp;log&nbsp;<i>n</i>) algorithm is used even for prime sizes.
Chris@10 102
Chris@10 103 <p>Each dimension has a <dfn>kind</dfn> parameter, of type
Chris@10 104 <code>fftw_r2r_kind</code>, specifying the kind of r2r transform to be used
Chris@10 105 for that dimension.
Chris@10 106 <a name="index-kind-_0028r2r_0029-70"></a><a name="index-fftw_005fr2r_005fkind-71"></a>(In the case of <code>fftw_plan_r2r</code>, this is an array <code>kind[rank]</code>
Chris@10 107 where <code>kind[i]</code> is the transform kind for the dimension
Chris@10 108 <code>n[i]</code>.) The kind can be one of a set of predefined constants,
Chris@10 109 defined in the following subsections.
Chris@10 110
Chris@10 111 <p>In other words, FFTW computes the separable product of the specified
Chris@10 112 r2r transforms over each dimension, which can be used e.g. for partial
Chris@10 113 differential equations with mixed boundary conditions. (For some r2r
Chris@10 114 kinds, notably the halfcomplex DFT and the DHT, such a separable
Chris@10 115 product is somewhat problematic in more than one dimension, however,
Chris@10 116 as is described below.)
Chris@10 117
Chris@10 118 <p>In the current version of FFTW, all r2r transforms except for the
Chris@10 119 halfcomplex type are computed via pre- or post-processing of
Chris@10 120 halfcomplex transforms, and they are therefore not as fast as they
Chris@10 121 could be. Since most other general DCT/DST codes employ a similar
Chris@10 122 algorithm, however, FFTW's implementation should provide at least
Chris@10 123 competitive performance.
Chris@10 124
Chris@10 125 <!-- =========> -->
Chris@10 126 </body></html>
Chris@10 127