<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Discrete Transforms — CVXOPT User's Guide</title>
<link rel="stylesheet" href="_static/cvxopt.css" type="text/css" />
<link rel="stylesheet" href="_static/pygments.css" type="text/css" />
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT: '#',
VERSION: '1.1.1',
COLLAPSE_MODINDEX: false,
FILE_SUFFIX: '.html',
HAS_SOURCE: false
};
</script>
<script type="text/javascript" src="_static/jquery.js"></script>
<script type="text/javascript" src="_static/doctools.js"></script>
<link rel="copyright" title="Copyright" href="copyright.html" />
<link rel="top" title="CVXOPT User's Guide" href="index.html" />
<link rel="next" title="Sparse Linear Equations" href="spsolvers.html" />
<link rel="prev" title="The LAPACK Interface" href="lapack.html" />
</head>
<body>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="spsolvers.html" title="Sparse Linear Equations"
accesskey="N">next</a></li>
<li class="right" >
<a href="lapack.html" title="The LAPACK Interface"
accesskey="P">previous</a> |</li>
<li><a href="http://abel.ee.ucla.edu/cvxopt">CVXOPT home</a> |</li>
<li><a href="index.html">user's guide</a> </li>
</ul>
</div>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body">
<div class="section" id="discrete-transforms">
<span id="c-fftw"></span><h1>Discrete Transforms<a class="headerlink" href="#discrete-transforms" title="Permalink to this headline">¶</a></h1>
<p>The <tt class="xref docutils literal"><span class="pre">cvxopt.fftw</span></tt> module is an interface to the FFTW library and
contains routines for discrete Fourier, cosine, and sine transforms.
This module is optional, and only installed when the FFTW library is made
available during the CVXOPT installation.</p>
<div class="admonition-see-also admonition seealso">
<p class="first admonition-title">See also</p>
<p class="last"><a class="reference external" href="http://www.fftw.org">FFTW3 code, documentation, copyright and license</a></p>
</div>
<div class="section" id="discrete-fourier-transform">
<h2>Discrete Fourier Transform<a class="headerlink" href="#discrete-fourier-transform" title="Permalink to this headline">¶</a></h2>
<dl class="function">
<dt id="cvxopt.fftw.dft">
<tt class="descclassname">cvxopt.fftw.</tt><tt class="descname">dft</tt><big>(</big><em>X</em><big>)</big><a class="headerlink" href="#cvxopt.fftw.dft" title="Permalink to this definition">¶</a></dt>
<dd><p>Replaces the columns of a dense complex matrix with their discrete
Fourier transforms: if <tt class="docutils literal"><span class="pre">X</span></tt> has <img class="math" src="_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n"/> rows,</p>
<div class="math">
<p><img src="_images/math/8c7f7085c27a8d4d39ad8afca40a774a78a91a82.png" alt="X[k,:] := \sum_{j=0}^{n-1} e^{-2\pi j k \sqrt{-1}/n} X[j,:],
\qquad k=0,\ldots,n-1." /></p>
</div></dd></dl>
<dl class="function">
<dt id="cvxopt.fftw.idft">
<tt class="descclassname">cvxopt.fftw.</tt><tt class="descname">idft</tt><big>(</big><em>X</em><big>)</big><a class="headerlink" href="#cvxopt.fftw.idft" title="Permalink to this definition">¶</a></dt>
<dd><p>Replaces the columns of a dense complex matrix with their inverse
discrete Fourier transforms: if <tt class="docutils literal"><span class="pre">X</span></tt> has <img class="math" src="_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n"/> rows,</p>
<div class="math">
<p><img src="_images/math/5a1dc1e6030606b400ca3bbfb30051f6035092c4.png" alt="X[k,:] :=
\frac{1}{n} \sum_{j=0}^{n-1} e^{2\pi j k \sqrt{-1}/n} X[j,:],
\qquad k=0,\ldots,n-1." /></p>
</div></dd></dl>
<p>The module also includes a discrete <em>N</em>-dimensional Fourier transform.
The input matrix is interpreted as an <em>N</em>-dimensional matrix stored
in column-major order. The discrete <em>N</em>-dimensional Fourier transform
computes the corresponding one-dimensional transform along each dimension.
For example, the two-dimensional transform applies a one-dimensional
transform to all the columns of the matrix, followed by a one-dimensional
transform to all the rows of the matrix.</p>
<dl class="function">
<dt id="cvxopt.fftw.dftn">
<tt class="descclassname">cvxopt.fftw.</tt><tt class="descname">dftn</tt><big>(</big><em>X</em><span class="optional">[</span>, <em>dims = X.size</em><span class="optional">]</span><big>)</big><a class="headerlink" href="#cvxopt.fftw.dftn" title="Permalink to this definition">¶</a></dt>
<dd>Replaces a dense complex matrix with its <em>N</em>-dimensional discrete
Fourier transform. The dimensions of the <em>N</em>-dimensional matrix
are given by the <em>N</em>-tuple <tt class="docutils literal"><span class="pre">dims</span></tt>. The two-dimensional transform is
computed as <tt class="docutils literal"><span class="pre">dftn(X,</span> <span class="pre">X.size)</span></tt>.</dd></dl>
<dl class="function">
<dt id="cvxopt.fftw.idftn">
<tt class="descclassname">cvxopt.fftw.</tt><tt class="descname">idftn</tt><big>(</big><em>X</em><span class="optional">[</span>, <em>dims = X.size</em><span class="optional">]</span><big>)</big><a class="headerlink" href="#cvxopt.fftw.idftn" title="Permalink to this definition">¶</a></dt>
<dd>Replaces a dense complex <em>N</em>-dimensional matrix with its inverse
<em>N</em>-dimensional discrete Fourier transform. The dimensions of the
matrix are given by the tuple <tt class="docutils literal"><span class="pre">dims</span></tt>. The two-dimensional inverse
transform is computed as <tt class="docutils literal"><span class="pre">idftn(X,</span> <span class="pre">X.size)</span></tt>.</dd></dl>
</div>
<div class="section" id="discrete-cosine-transform">
<h2>Discrete Cosine Transform<a class="headerlink" href="#discrete-cosine-transform" title="Permalink to this headline">¶</a></h2>
<dl class="function">
<dt id="cvxopt.fftw.dct">
<tt class="descclassname">cvxopt.fftw.</tt><tt class="descname">dct</tt><big>(</big><em>X</em><span class="optional">[</span>, <em>type = 2</em><span class="optional">]</span><big>)</big><a class="headerlink" href="#cvxopt.fftw.dct" title="Permalink to this definition">¶</a></dt>
<dd><p>Replaces the columns of a dense real matrix with their discrete
cosine transforms. The second argument, an integer between 1 and 4,
denotes the type of transform (DCT-I, DCT-II, DCT-III, DCT-IV).
The DCT-I transform requires that the row dimension of <tt class="docutils literal"><span class="pre">X</span></tt> is at
least 2. These transforms are defined as follows (for a matrix with
<img class="math" src="_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n"/> rows).</p>
<div class="math">
<p><img src="_images/math/6195631f3fbcda2f8278cb0969ad0855c9bbcb9a.png" alt="\mbox{DCT-I:} \qquad
X[k,:] & := X[0,:] + (-1)^k X[n-1,:] +
2 \sum_{j=1}^{n-2} X[j,:] \cos(\pi j k /(n-1)),
\qquad k=0,\ldots,n-1.\\
\mbox{DCT-II:} \qquad
X[k,:] & := 2 \sum_{j=0}^{n-1} X[j,:] \cos(\pi(j+1/2)k/n),
\qquad k=0,\ldots,n-1.\\
\mbox{DCT-III:} \qquad
X[k,:] & :=
X[0,:] + 2 \sum_{j=1}^{n-1} X[j,:] \cos(\pi j(k+1/2)/n),
\qquad k=0,\ldots,n-1.\\
\mbox{DCT-IV:} \qquad
X[k,:] & :=
2 \sum_{j=0}^{n-1} X[j,:] \cos(\pi (j+1/2)(k+1/2)/n),
\qquad k=0,\ldots,n-1." /></p>
</div></dd></dl>
<dl class="function">
<dt id="cvxopt.fftw.idct">
<tt class="descclassname">cvxopt.fftw.</tt><tt class="descname">idct</tt><big>(</big><em>X</em><span class="optional">[</span>, <em>type = 2</em><span class="optional">]</span><big>)</big><a class="headerlink" href="#cvxopt.fftw.idct" title="Permalink to this definition">¶</a></dt>
<dd>Replaces the columns of a dense real matrix with the inverses
of the discrete cosine transforms defined above.</dd></dl>
<p>The module also includes a discrete <em>N</em>-dimensional cosine transform.
The input matrix is interpreted as an <em>N</em>-dimensional matrix stored
in column-major order. The discrete <em>N</em>-dimensional cosine transform
computes the corresponding one-dimensional transform along each dimension.
For example, the two-dimensional transform applies a one-dimensional
transform to all the rows of the matrix, followed by a one-dimensional
transform to all the columns of the matrix.</p>
<dl class="function">
<dt id="cvxopt.fftw.dctn">
<tt class="descclassname">cvxopt.fftw.</tt><tt class="descname">dctn</tt><big>(</big><em>X</em><span class="optional">[</span>, <em>dims = X.size</em>, <em>type = 2</em><span class="optional">]</span><big>)</big><a class="headerlink" href="#cvxopt.fftw.dctn" title="Permalink to this definition">¶</a></dt>
<dd>Replaces a dense real matrix with its <em>N</em>-dimensional discrete cosine
transform. The dimensions of the <em>N</em>-dimensional matrix are given by
the <em>N</em>-tuple <tt class="docutils literal"><span class="pre">dims</span></tt>. The two-dimensional transform is computed as
<tt class="docutils literal"><span class="pre">dctn(X,</span> <span class="pre">X.size)</span></tt>.</dd></dl>
<dl class="function">
<dt id="cvxopt.fftw.idctn">
<tt class="descclassname">cvxopt.fftw.</tt><tt class="descname">idctn</tt><big>(</big><em>X</em><span class="optional">[</span>, <em>dims = X.size</em>, <em>type = 2</em><span class="optional">]</span><big>)</big><a class="headerlink" href="#cvxopt.fftw.idctn" title="Permalink to this definition">¶</a></dt>
<dd>Replaces a dense real <em>N</em>-dimensional matrix with its inverse
<em>N</em>-dimensional discrete cosine transform. The dimensions of the
matrix are given by the tuple <tt class="docutils literal"><span class="pre">dims</span></tt>. The two-dimensional inverse
transform is computed as <tt class="docutils literal"><span class="pre">idctn(X,</span> <span class="pre">X.size)</span></tt>.</dd></dl>
</div>
<div class="section" id="discrete-sine-transform">
<h2>Discrete Sine Transform<a class="headerlink" href="#discrete-sine-transform" title="Permalink to this headline">¶</a></h2>
<dl class="function">
<dt id="cvxopt.fftw.dst">
<tt class="descclassname">cvxopt.fftw.</tt><tt class="descname">dst</tt><big>(</big><em>X</em>, <em>dims</em><span class="optional">[</span>, <em>type = 1</em><span class="optional">]</span><big>)</big><a class="headerlink" href="#cvxopt.fftw.dst" title="Permalink to this definition">¶</a></dt>
<dd><p>Replaces the columns of a dense real matrix with their discrete
sine transforms. The second argument, an integer between 1 and 4,
denotes the type of transform (DST-I, DST-II, DST-III, DST-IV).
These transforms are defined as follows (for a matrix with <img class="math" src="_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n"/>
rows).</p>
<div class="math">
<p><img src="_images/math/64165d10cadf321ef6baf505ec44eaeb5506a363.png" alt="\mbox{DST-I:} \qquad
X[k,:] & :=
2 \sum_{j=0}^{n-1} X[j,:] \sin(\pi(j+1)(k+1)/(n+1)),
\qquad k=0,\ldots,n-1.\\
\mbox{DST-II:} \qquad
X[k,:] & := 2 \sum_{j=0}^{n-1} X[j,:] \sin(\pi(j+1/2)(k+1)/n),
\qquad k=0,\ldots,n-1.\\
\mbox{DST-III:} \qquad
X[k,:] & := (-1)^k X[n-1,:] + 2 \sum_{j=0}^{n-2}
X[j,:] \sin(\pi(j+1)(k+1/2)/n), \qquad k=0,\ldots,n-1. \\
\mbox{DST-IV:} \qquad
X[k,:] & :=
2 \sum_{j=0}^{n-1} X[j,:] \sin(\pi (j+1/2)(k+1/2)/n),
\qquad k=0,\ldots,n-1." /></p>
</div></dd></dl>
<dl class="function">
<dt id="cvxopt.fftw.idst">
<tt class="descclassname">cvxopt.fftw.</tt><tt class="descname">idst</tt><big>(</big><em>X</em>, <em>dims</em><span class="optional">[</span>, <em>type = 1</em><span class="optional">]</span><big>)</big><a class="headerlink" href="#cvxopt.fftw.idst" title="Permalink to this definition">¶</a></dt>
<dd>Replaces the columns of a dense real matrix with the inverses of the
discrete sine transforms defined above.</dd></dl>
<p>The module also includes a discrete <em>N</em>-dimensional sine transform. The
input matrix is interpreted as an <em>N</em>-dimensional matrix stored in
column-major order. The discrete <em>N</em>-dimensional sine transform computes
the corresponding one-dimensional transform along each dimension. For
example, the two-dimensional transform applies a one-dimensional
transform to all the rows of the matrix, followed by a one-dimensional
transform to all the columns of the matrix.</p>
<dl class="function">
<dt id="cvxopt.fftw.dstn">
<tt class="descclassname">cvxopt.fftw.</tt><tt class="descname">dstn</tt><big>(</big><em>X</em><span class="optional">[</span>, <em>dims = X.size</em>, <em>type = 2</em><span class="optional">]</span><big>)</big><a class="headerlink" href="#cvxopt.fftw.dstn" title="Permalink to this definition">¶</a></dt>
<dd>Replaces a dense real matrix with its <em>N</em>-dimensional discrete sine
transform. The dimensions of the <em>N</em>-dimensional matrix are given by
the <em>N</em>-tuple <tt class="docutils literal"><span class="pre">dims</span></tt>. The two-dimensional transform is computed as
<tt class="docutils literal"><span class="pre">dstn(X,</span> <span class="pre">X.size)</span></tt>.</dd></dl>
<dl class="function">
<dt id="cvxopt.fftw.idstn">
<tt class="descclassname">cvxopt.fftw.</tt><tt class="descname">idstn</tt><big>(</big><em>X</em><span class="optional">[</span>, <em>dims = X.size</em>, <em>type = 2</em><span class="optional">]</span><big>)</big><a class="headerlink" href="#cvxopt.fftw.idstn" title="Permalink to this definition">¶</a></dt>
<dd>Replaces a dense real <em>N</em>-dimensional matrix with its inverse
<em>N</em>-dimensional discrete sine transform. The dimensions of the
matrix are given by the tuple <tt class="docutils literal"><span class="pre">dims</span></tt>. The two-dimensional inverse
transform is computed as <tt class="docutils literal"><span class="pre">idstn(X,</span> <span class="pre">X.size)</span></tt>.</dd></dl>
</div>
</div>
</div>
</div>
</div>
<div class="sphinxsidebar">
<div class="sphinxsidebarwrapper">
<h3><a href="index.html">Table Of Contents</a></h3>
<ul>
<li><a class="reference external" href="#">Discrete Transforms</a><ul>
<li><a class="reference external" href="#discrete-fourier-transform">Discrete Fourier Transform</a></li>
<li><a class="reference external" href="#discrete-cosine-transform">Discrete Cosine Transform</a></li>
<li><a class="reference external" href="#discrete-sine-transform">Discrete Sine Transform</a></li>
</ul>
</li>
</ul>
<h4>Previous topic</h4>
<p class="topless"><a href="lapack.html"
title="previous chapter">The LAPACK Interface</a></p>
<h4>Next topic</h4>
<p class="topless"><a href="spsolvers.html"
title="next chapter">Sparse Linear Equations</a></p>
<div id="searchbox" style="display: none">
<h3>Quick search</h3>
<form class="search" action="search.html" method="get">
<input type="text" name="q" size="18" />
<input type="submit" value="Go" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
<p class="searchtip" style="font-size: 90%">
Enter search terms or a module, class or function name.
</p>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="spsolvers.html" title="Sparse Linear Equations"
>next</a></li>
<li class="right" >
<a href="lapack.html" title="The LAPACK Interface"
>previous</a> |</li>
<li><a href="http://abel.ee.ucla.edu/cvxopt">CVXOPT home</a> |</li>
<li><a href="index.html">user's guide</a> </li>
</ul>
</div>
<div class="footer">
Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 0.6.5.
</div>
</body>
</html>
