{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:46:12Z","timestamp":1776797172275,"version":"3.51.2"},"reference-count":26,"publisher":"American Mathematical Society (AMS)","issue":"289","license":[{"start":{"date-parts":[[2015,2,11]],"date-time":"2015-02-11T00:00:00Z","timestamp":1423612800000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    We propose a fast discrete Fourier transform for a given data set which may be generated from sampling a function of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"d\">\n                        <mml:semantics>\n                          <mml:mi>d<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">d<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -variables on a sparse grid and a fast discrete backward Fourier transform on a hyperbolic cross index set. Computation of these transforms can be formulated as evaluation of\n                    <italic>dimension-reducible<\/italic>\n                    sums on sparse grids. We introduce a fast algorithm for evaluating such sums and prove that the total number of operations needed in the algorithm is\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script upper O left-parenthesis n log Superscript d Baseline n right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi class=\"MJX-tex-caligraphic\" mathvariant=\"script\">O<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:msup>\n                              <mml:mi>log<\/mml:mi>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mi>d<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathcal {O}(n\\log ^{d}n)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , where\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n\">\n                        <mml:semantics>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    is the number of components along each coordinate direction of the data set. We then use it to develop fast algorithms for computing the discrete Fourier transform on the sparse grid and the discrete backward Fourier transform on the hyperbolic cross index set. We also show that if the given data set is sampled from a function having regularity of order\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"s\">\n                        <mml:semantics>\n                          <mml:mi>s<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">s<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , then its discrete Fourier transform has the optimal approximation order\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script upper O left-parenthesis n Superscript negative s Baseline right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi class=\"MJX-tex-caligraphic\" mathvariant=\"script\">O<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>n<\/mml:mi>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mo>\n                                  \u2212\n                                  \n                                <\/mml:mo>\n                                <mml:mi>s<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathcal {O}(n^{-s})<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . Numerical examples are presented to demonstrate the approximation accuracy and computational efficiency of the proposed algorithms.\n                  <\/p>","DOI":"10.1090\/s0025-5718-2014-02785-3","type":"journal-article","created":{"date-parts":[[2014,2,11]],"date-time":"2014-02-11T10:29:48Z","timestamp":1392114588000},"page":"2347-2384","source":"Crossref","is-referenced-by-count":4,"title":["Fast computation of the multidimensional discrete Fourier transform and discrete backward Fourier transform on sparse grids"],"prefix":"10.1090","volume":"83","author":[{"given":"Ying","family":"Jiang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuesheng","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2014,2,11]]},"reference":[{"issue":"3","key":"1","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1137\/S1064827593247035","article-title":"The solution of multidimensional real Helmholtz equations on sparse grids","volume":"17","author":"Balder, Robert","year":"1996","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"issue":"4","key":"2","doi-asserted-by":"publisher","first-page":"1192","DOI":"10.1137\/S1064827596309098","article-title":"Fast algorithms for periodic spline wavelets on sparse grids","volume":"20","author":"Bittner, Kai","year":"1999","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"key":"3","first-page":"63","article-title":"A multigrid algorithm for higher order finite elements on sparse grids","volume":"6","author":"Bungartz, Hans-Joachim","year":"1997","journal-title":"Electron. Trans. Numer. Anal."},{"key":"4","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1017\/S0962492904000182","article-title":"Sparse grids","volume":"13","author":"Bungartz, Hans-Joachim","year":"2004","journal-title":"Acta Numer.","ISSN":"https:\/\/id.crossref.org\/issn\/0962-4929","issn-type":"print"},{"issue":"4","key":"5","doi-asserted-by":"publisher","first-page":"1965","DOI":"10.1137\/070703478","article-title":"A fast Fourier-Galerkin method for solving singular boundary integral equations","volume":"46","author":"Cai, Haotao","year":"2008","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"228","key":"6","doi-asserted-by":"publisher","first-page":"1569","DOI":"10.1090\/S0025-5718-99-01110-2","article-title":"A construction of interpolating wavelets on invariant sets","volume":"68","author":"Chen, Zhongying","year":"1999","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"7","doi-asserted-by":"publisher","first-page":"297","DOI":"10.2307\/2003354","article-title":"An algorithm for the machine calculation of complex Fourier series","volume":"19","author":"Cooley, James W.","year":"1965","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"3","key":"8","first-page":"36","article-title":"Multidimensional approximations by trigonometric polynomials with harmonics of a hyperbolic cross","volume":"56","author":"Devor, R. A.","year":"1994","journal-title":"Mat. Zametki","ISSN":"https:\/\/id.crossref.org\/issn\/0025-567X","issn-type":"print"},{"issue":"6","key":"9","doi-asserted-by":"publisher","first-page":"4415","DOI":"10.1137\/090754947","article-title":"Nonequispaced hyperbolic cross fast Fourier transform","volume":"47","author":"D\u00f6hler, Michael","year":"2010","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"1","key":"10","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1006\/jcom.1996.0004","article-title":"Information complexity of multivariate Fredholm integral equations in Sobolev classes","volume":"12","author":"Frank, Karin","year":"1996","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"1","key":"11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00607-007-0225-3","article-title":"Fourier transform on sparse grids: code design and the time dependent Schr\u00f6dinger equation","volume":"80","author":"Gradinaru, V.","year":"2007","journal-title":"Computing","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"issue":"1","key":"12","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1137\/050629823","article-title":"Strang splitting for the time-dependent Schr\u00f6dinger equation on sparse grids","volume":"46","author":"Gradinaru, V.","year":"2007","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"268","key":"13","doi-asserted-by":"publisher","first-page":"2223","DOI":"10.1090\/S0025-5718-09-02248-0","article-title":"Optimized general sparse grid approximation spaces for operator equations","volume":"78","author":"Griebel, M.","year":"2009","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"14","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF01385849","article-title":"Fouriertransformation auf d\u00fcnnen Gittern mit hierarchischen Basen","volume":"63","author":"Hallatschek, Klaus","year":"1992","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"1","key":"15","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.jco.2009.10.001","article-title":"Fast discrete algorithms for sparse Fourier expansions of high dimensional functions","volume":"26","author":"Jiang, Ying","year":"2010","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"9","key":"16","doi-asserted-by":"publisher","first-page":"2792","DOI":"10.1016\/j.cam.2010.01.022","article-title":"Fast Fourier-Galerkin methods for solving singular boundary integral equations: numerical integration and precondition","volume":"234","author":"Jiang, Ying","year":"2010","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"},{"issue":"5","key":"17","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1016\/j.jco.2011.03.003","article-title":"B-spline quasi-interpolation on sparse grids","volume":"27","author":"Jiang, Ying","year":"2011","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"18","unstructured":"S. Knapek, Hyperbolic cross approximation of integral operators with smooth kernel, Technical Report 665, SFB 256, Univ. Bonn, 2000."},{"key":"19","first-page":"395","article-title":"Approximation of differentiable functions of several variables by Fourier sums in the \ud835\udc3f_{\ud835\udc5d} metric","volume":"15","author":"Nikol\u2032skaja, N. S.","year":"1974","journal-title":"Sibirsk. Mat. \\v{Z}.","ISSN":"https:\/\/id.crossref.org\/issn\/0037-4474","issn-type":"print"},{"issue":"1","key":"20","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/BF00970164","article-title":"Hyperbolic cross and complexity of an approximate solution of Fredholm integral equations of the second kind with differentiable kernels","volume":"32","author":"Pereverzev, S. V.","year":"1991","journal-title":"Sibirsk. Mat. Zh.","ISSN":"https:\/\/id.crossref.org\/issn\/0037-4474","issn-type":"print"},{"issue":"6","key":"21","doi-asserted-by":"publisher","first-page":"3228","DOI":"10.1137\/100787842","article-title":"Efficient spectral sparse grid methods and applications to high-dimensional elliptic problems","volume":"32","author":"Shen, Jie","year":"2010","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"key":"22","first-page":"113","article-title":"Approximations of functions with bounded mixed derivative","volume":"178","author":"Temlyakov, V. N.","year":"1986","journal-title":"Trudy Mat. Inst. Steklov.","ISSN":"https:\/\/id.crossref.org\/issn\/0371-9685","issn-type":"print"},{"key":"23","series-title":"Computational Mathematics and Analysis Series","isbn-type":"print","volume-title":"Approximation of periodic functions","author":"Temlyakov, V. N.","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/1560721316"},{"issue":"1","key":"24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11425-010-0014-x","article-title":"Fast Fourier-Galerkin methods for first-kind logarithmic-kernel integral equations on open arcs","volume":"53","author":"Wang, Bo","year":"2010","journal-title":"Sci. China Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1674-7283","issn-type":"print"},{"issue":"1","key":"25","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1216\/jiea\/1181075260","article-title":"Fast Boolean approximation methods for solving integral equations in high dimensions","volume":"16","author":"Xu, Yuesheng","year":"2004","journal-title":"J. Integral Equations Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0897-3962","issn-type":"print"},{"issue":"3","key":"26","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/s10915-010-9438-2","article-title":"Fast matrix-vector multiplication in the sparse-grid Galerkin method","volume":"47","author":"Zeiser, Andreas","year":"2011","journal-title":"J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0885-7474","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2014-83-289\/S0025-5718-2014-02785-3\/S0025-5718-2014-02785-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2014-83-289\/S0025-5718-2014-02785-3\/S0025-5718-2014-02785-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:02:14Z","timestamp":1776794534000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2014-83-289\/S0025-5718-2014-02785-3\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2,11]]},"references-count":26,"journal-issue":{"issue":"289","published-print":{"date-parts":[[2014,9]]}},"alternative-id":["S0025-5718-2014-02785-3"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2014-02785-3","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2014,2,11]]}}}