<!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>