(************** Content-type: application/mathematica ************** Mathematica-Compatible Notebook This notebook can be used with any Mathematica-compatible application, such as Mathematica, MathReader or Publicon. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. *******************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 50728, 1256]*) (*NotebookOutlinePosition[ 51788, 1292]*) (* CellTagsIndexPosition[ 51677, 1285]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell[TextData[StyleBox["Fast Fourier Transform \non Nonequispaced Grid", FontSize->24, FontWeight->"Bold", FontSlant->"Plain", FontColor->RGBColor[0.500008, 0, 0.500008]]], "Subsubtitle", TextAlignment->Center, TextJustification->0], Cell[CellGroupData[{ Cell[TextData[{ " ", StyleBox["The Package", FontColor->RGBColor[0.500008, 0, 0.250004]], " ", StyleBox["NUFourier", FontFamily->"Courier New", FontSize->36, FontColor->RGBColor[0, 0.250004, 0.500008]] }], "Section"], Cell[BoxData[{ RowBox[{\( (*\(:\)\(Name : NumericalMath`NUFourier`\)*) \), " ", "\[IndentingNewLine]", \( (*\(:\)\(Title : \ Fast\ Fourier\ Transform\ on\ nonequispaced\ grid\)*) \), "\[IndentingNewLine]", \( (*\(\(:\)\(Author : \ Anry\ Nersessian\)\), \ Institute\ of\ Mathematics\ \n\t\t\ \ \ of\ National\ Academy\ of\ \ Sciences\ of\ Armenia*) \), "\[IndentingNewLine]", RowBox[{"(*", RowBox[{ RowBox[{":", RowBox[{"Summary", ":", RowBox[{"This", " ", StyleBox[ RowBox[{"p", StyleBox["ackage", FontFamily->"Courier New"]}]], StyleBox[" ", FontFamily->"Courier New"], StyleBox["calculates", FontFamily->"Courier New"], StyleBox[" ", FontFamily->"Courier New"], StyleBox["the", FontFamily->"Courier New"], StyleBox[" ", FontFamily->"Courier New"], StyleBox["list", FontFamily->"Courier New"], StyleBox[ RowBox[{ StyleBox[" ", FontFamily->"Courier New"], " "}]], \(\[Sum]\+\(k = 1\)\%N\( f\_k\) E\^\(I\ \[Pi]\ \(t\_k\) w\_j\)\)}]}]}], ",", " ", \(j = 1\), ",", RowBox[{ RowBox[{ "...", "M", " ", "with", " ", "a", " ", "given", " ", "precision", " ", StyleBox["for", FontFamily->"Courier New"], StyleBox[" ", FontFamily->"Courier New"], StyleBox["the", FontFamily->"Courier New"], StyleBox[" ", FontFamily->"Courier New"], StyleBox["given", FontFamily->"Courier New"], StyleBox[" ", FontFamily->"Courier New"], StyleBox["complex", FontFamily->"Courier New"], StyleBox[" ", FontFamily->"Courier New"], StyleBox["valued", FontFamily->"Courier New"], StyleBox[" ", FontFamily->"Courier New"], StyleBox["listf", FontFamily->"Courier New"]}], StyleBox["=", FontFamily->"Courier New"], RowBox[{ StyleBox["{", FontFamily->"Courier New"], \(f\_k\), StyleBox["}", FontFamily->"Courier New"]}]}], StyleBox[",", FontFamily->"Courier New"], StyleBox[" ", FontFamily->"Courier New"], RowBox[{ StyleBox[\(real\ list\ t\), FontFamily->"Courier New"], StyleBox["=", FontFamily->"Courier New"], RowBox[{ StyleBox["{", FontFamily->"Courier New"], \(t\_k\), StyleBox["}", FontFamily->"Courier New"]}]}], ",", StyleBox[\(k = 1\), FontFamily->"Courier New"], StyleBox[",", FontFamily->"Courier New"], StyleBox["2", FontFamily->"Courier New"], StyleBox[",", FontFamily->"Courier New"], StyleBox["..", FontFamily->"Courier New"], StyleBox[",", FontFamily->"Courier New"], RowBox[{ StyleBox[\(N\ and\ real\ list\ w\), FontFamily->"Courier New"], StyleBox["=", FontFamily->"Courier New"], RowBox[{ StyleBox["{", FontFamily->"Courier New"], \(w\_k\), StyleBox["}", FontFamily->"Courier New"]}]}], ",", " ", StyleBox[\(k = 1\), FontFamily->"Courier New"], StyleBox[",", FontFamily->"Courier New"], StyleBox["2", FontFamily->"Courier New"], StyleBox[",", FontFamily->"Courier New"], StyleBox["..", FontFamily->"Courier New"], StyleBox[",", FontFamily->"Courier New"], StyleBox[\(\(M\)\(.\)\), FontFamily->"Courier New"]}], StyleBox[" ", FontFamily->"Courier New"], "*)"}], "\[IndentingNewLine]", \( (*\(:\)\(Context : NumericalMath`NUFourier`\)*) \), "\n", \( (*\(:\)\(Mathematica\ \(Version : \ 4.1\)\)*) \), "\n", \( (*\(:\)\(Package\ \(Version : \ Alpha\ 1\)\)*) \), "\n", \( (*\(:\)\(Copyright : \ Copyright\ 2002\)*) \), "\[IndentingNewLine]", \( (*\(\(:\)\(History : \n\t\ Preliminary\ \ package\ \((version\ Alpha\ Zero)\)\ was\)\)\[IndentingNewLine]\ developed\ \ in\ 1998\ by\ Anry\ Nersessian\ \n\ \ \ \ \((Institute\ \ of\ Mathematics\ of\ National\ Academy\ of\ Sciences\[IndentingNewLine]of\ \ Armenia)\) . \n\t\ Current\ version\ is\ developed\ by\ Anry\ \ Nersessian\ \ in\ \[IndentingNewLine]assistance\ with\ Arnak\ Poghosyan, \ Institute\ of\ Mathematics\ of\ \[IndentingNewLine]\ \ National\ \ Academy\ of\ Sciences\ of\ Armenia, \ November\ 2002. \ \t\n\ *) \), "\[IndentingNewLine]", "\n", " ", \( (*\(\(:\)\(Keywords : \ FFT\)\), \ DFT, \ Fast\ Algorithms, \ Nonuniform\ grid*) \), "\[IndentingNewLine]", "\n", "\t", \( (*\(\(:\)\(Sources : \[IndentingNewLine]\ \ \ 1. \ A . Dutt\)\), V . Rokhlin, Fast\ Fourier\ Transforms\ for\ nonequispaced\ data, Siam\ J . Sci . Comput . , vol\ 14, No\ 6, \(pp . 1368 - 1393. \n \ \ \ \ \ \ 2. \ Nersessian\ A . B\), Quasiexponential\ function\ and\ Fourier\ QuasiTransforms, DNAN\ Armenii\ \((Reports\ of\ the\ National\ Academy\ of\ Sciences\ \ of\ the\ Republic\ of\ Armenia)\), vol\ 101, No\ 1, pp . 5 - 11. \n\t\ *) \), "\[IndentingNewLine]", "\n", \( (*Warning : \ The\ package\ works\ best\ if \((max {t\_k} - min {t\_k})\) \((max {w\_k} - min {w\_k})\) \[LessEqual] 20\ N*) \), "\[IndentingNewLine]", "\[IndentingNewLine]", "\[IndentingNewLine]", \ \(BeginPackage["\"];\)}], "\[IndentingNewLine]", \ \(NUFourier::incsh = "\";\), "\ \[IndentingNewLine]", RowBox[{ RowBox[{\(NUFourier::warn\), "=", "\"\<\!\(\* StyleBox[\"NUFourier\",\nFontFamily->\"Courier New\",\n\ FontVariations->{\"CompatibilityType\"->0}]\)\!\(\* StyleBox[\"[\",\nFontFamily->\"Courier New\",\n\ FontVariations->{\"CompatibilityType\"->0}]\)\!\(\* StyleBox[\"f\",\nFontFamily->\"Courier New\",\n\ FontVariations->{\"CompatibilityType\"->0}]\)\!\(\* StyleBox[\",\",\nFontFamily->\"Courier New\",\n\ FontVariations->{\"CompatibilityType\"->0}]\)\!\(\* StyleBox[\"{\",\nFontFamily->\"Courier New\",\n\ FontVariations->{\"CompatibilityType\"->0}]\)\!\(\* StyleBox[\"t\",\nFontFamily->\"Courier New\",\n\ FontVariations->{\"CompatibilityType\"->0}]\)\!\(\* StyleBox[\",\",\nFontFamily->\"Courier New\",\n\ FontVariations->{\"CompatibilityType\"->0}]\)\!\(\* StyleBox[\"w\",\nFontFamily->\"Courier New\",\n\ FontVariations->{\"CompatibilityType\"->0}]\)\!\(\* StyleBox[\"}\",\nFontFamily->\"Courier New\",\n\ FontVariations->{\"CompatibilityType\"->0}]\)\!\(\* StyleBox[\"]\",\nFontFamily->\"Courier New\",\n\ FontVariations->{\"CompatibilityType\"->0}]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\",\nFontWeight->\"Bold\"]\)\!\(\* StyleBox[\"works\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"best\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"if\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"(\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"max\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"{\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\(t\_k\),\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"}\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"-\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"min\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"{\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\(t\_k\),\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"}\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\")\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"(\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"max\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"{\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\(w\_k\),\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"}\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"-\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"min\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"{\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\(w\_k\),\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"}\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\")\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"\[LessEqual]\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"20\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"N\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\",\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"where\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"N\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"=\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"Length\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"[\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"f\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"]\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\".\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"Otherwise\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"the\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"program\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"works\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"slow\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\".\",\nFontFamily->\"Courier New\"]\)\>\""}], ";"}], "\[IndentingNewLine]", RowBox[{\(Off[General::"\"];\), " ", "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{\(NUFourier::usage\), "=", "\"\\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"the\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"given\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"complex\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"valued\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"list\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"f\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"=\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"{\",\nFontFamily->\"Courier New\"]\)\!\(f\_k\)\!\(\* StyleBox[\"}\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\",\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"real\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"list\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"t\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"=\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"{\",\nFontFamily->\"Courier New\"]\)\!\(t\_k\)\!\(\* StyleBox[\"}\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\",\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"k\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"=\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"1\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\",\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"2\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\",\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"..\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\",\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"N\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"and\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"real\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"list\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\" \",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"w\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"=\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"{\",\nFontFamily->\"Courier New\"]\)\!\(w\_k\)\!\(\* StyleBox[\"}\",\nFontFamily->\"Courier New\"]\), \!\(\* StyleBox[\"k\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"=\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"1\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\",\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"2\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\",\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"..\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\",\",\nFontFamily->\"Courier New\"]\)\!\(\* StyleBox[\"M\",\nFontFamily->\"Courier New\"]\).\>\""}], ";"}], "\[IndentingNewLine]", \(Options[ NUFourier] = {PrecisionGoal \[Rule] Automatic};\), "\[IndentingNewLine]", \ \(Begin["\<`Private`\>"];\), "\[IndentingNewLine]", \(dt[n_Integer, al_] := Table[\ Evaluate[E\^\(al\ k\^2\)], {k, \(-Floor[n/2]\), n - Floor[n/2] - 1}];\), "\n", \(per[l_List, p_Integer] := \n\t Block[{nn, lb, le}, \n\t\tnn = Length[l]; \n\t\tlb = Take[l, {1, p}]; \n\t\tle = Take[l, {nn - p + 1, nn}]; \n\t\tFlatten[{le, l, lb}]\n\t\t];\), "\n", \(ge[n_Integer, m_] := Table[0, {k, m\ n - 1 - Floor[\ m\ n/2] - n + Floor[n/2] + 1}];\), "\n", \(gb[ n_Integer, m_] := Table[0, {k, Floor[m\ n/2] - Floor[n/2]}];\), "\n", \(nul[ll_List, m_] := Flatten[{gb[Length[ll], m], ll, ge[Length[ll], m]}];\), "\n", \(lim[prec_] := Which[prec < 9, {prec, 70}, prec < 11, {prec, 80}, prec < 14, {prec, 100}, True, {prec, 120}];\), "\[IndentingNewLine]", \(in = Interpolation[Table[lim[prec], {prec, 0, 16}], InterpolationOrder \[Rule] 1];\), "\[IndentingNewLine]", RowBox[{\(flst[l_List] := Block[{fy, nn = Length[l]}, \n\tfy = RotateLeft[l, Floor[nn/2]]; \n RotateRight[Fourier[fy]/\@nn, Floor[nn/2]]];\), "\n"}], "\[IndentingNewLine]", RowBox[{\(tiv[t_List, m_, qq_] := Module[{nn, d, a, aa, aaa, e, b, c, nz, ss, pss}, \n nn = 2\ m\ \ qq; \nd = Ceiling[Sort[nn\ \ t + nn]]; \n a = Complement[Range[1, 2\ nn], d]; \n aa = Table[0. , {Length[a]}]; \naaa = Transpose[List[a, aa]]; \n e = Complement[Range[1, 2\ nn], a]; \nb = Split[d]; \n c = Table[Length[b[\([i]\)]], {i, 1, Length[b]}]; \n nz = Transpose[List[e, c]]; \n ss = Transpose[Sort[Join[nz, aaa]]] // Last; \n pss = Partition[ss, 2]; \n Table[Apply[Plus, pss[\([i]\)]], {i, 1, Length[pss]}]];\), "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{\(pe[al_, {f_List, t_List}, q_Integer, m_, qq_] := \n Module[{nn, s, zero, u, usum, l, ll, \[Alpha], \[Beta]}, \[IndentingNewLine]nn = Length[f]; \[IndentingNewLine]s = tiv[t, m, qq]; \[IndentingNewLine]zero = Table[0, {q}]; \[IndentingNewLine]u = Join[zero, s, zero]; \n usum = ReplacePart[FoldList[Plus[#1, #2] &, 0, u], 0, 1]; \n l = Range[\(-m\)\ qq - q/2, m\ qq + q/2]; \n ll = l + \ m\ qq + q/2 + 1; \[IndentingNewLine]\[Alpha] = Map[usum[\([#]\)] + 1\ &, ll]; \n\[Beta] = Map[usum[\([q + #]\)]\ &, ll]; \ \ \ \ \[IndentingNewLine]\[IndentingNewLine]\ \ \(\@\[Pi]\/\@al\) Table[\[Sum]\+\(k = \[Alpha][\([j + m\ qq + prec + 1]\)]\)\%\(\ \[Beta][\([j + m\ qq + prec + 1]\)]\)f[\([k]\)] E\^\(-\(\(\(\[Pi]\^2\) \((2\ m\ qq\ \ t[\([k]\)] - 2\ \ j)\)\^2\)\/\(4\ al\)\)\), {j, \(-m\)\ qq - prec, m\ qq + prec}]\[IndentingNewLine]\[IndentingNewLine]\ \[IndentingNewLine]];\), "\[IndentingNewLine]"}], "\n", RowBox[{\(superA2[w_List, f_List, prec_] := \n\t Module[{h, m, nn, al0, al2, al1, p, ce, al, a, aa, b, ll, lp, lr, lf, ww, le, lu, ls, lk, lq}, \[IndentingNewLine]h = 1; \[IndentingNewLine]m = 1.8; \[IndentingNewLine]nn = Length[f]; \[IndentingNewLine]al0 = \(h\ 2.3\ \ m\ \((prec)\)\)\ \/\((m - 1)\); \[IndentingNewLine]al2 = FindRoot[\ \@\(m\/2\ \ Sinh[\(2 \[Alpha]\)\/m]\)\%4 \[Equal] E\^\(\(-\ 1.15\)\ prec + \[Alpha]/2 + Log[\[Alpha]]/4\), {\ \[Alpha], al0, al0 + 1}, \[IndentingNewLine]MaxIterations \[Rule] 15]; \[IndentingNewLine]al1 = \((\(al2 // First\) // Last)\) + 1\/\(prec\^2 + 1\); \[IndentingNewLine]p = 2\ \((Round[\ \(\[Pi]\^\(-1\)\) \@al1\ \@\(2.3\ prec + \(0.25\ \ al1\)\/m\^2 - Log[4 al1/\[Pi]]/2\)\ \ ])\); \n\t\tce = Ceiling[p/2]; \[IndentingNewLine]\ \ \ \ \ \tal = al1\/nn\^2; \n\t\ta = \[Pi]^2/\((4\ al)\); \n\t\taa = 4 a/nn\^2; \n\t\tb = Floor[nn/2]; \n\t\tll = Table[k, {k, 0, p - 1}]; \n\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ lp = flst[f\ dt[nn, al]]; \n\t\tlr = per[lp, ce]; \n\t\tlf = Map[Evaluate[E^\((\(-aa\)\ #\^2)\)] &, ll]; \n\t\tww = Map[Evaluate[\(-2\)\ Ceiling[\(-\(p\/2\)\) + b\ #1] + nn\ #1] &, w]; \n\t\tle = Evaluate[Exp[\(-aa\)\ ww\^2/4]]; \n\t\tlu = Evaluate[Exp[aa\ ww]]; \n\t\tls = Map[Evaluate[\((Ceiling[b\ #\ \ - p/2] + 1 + ce + b)\)] &, w]; \n\t\tlk = Outer[lr[\([#1 + #2]\)] &, ll, ls]; \n\t\tlq = Map[Evaluate[lu]^#\ &, ll]; \n\t\t\(\[Sqrt]\[Pi]\/\[Sqrt]al\) Evaluate[le\ \ Apply[Plus, lf\ lq\ lk]]];\), "\n"}], "\n", \(NUFourier[f_, {w_, ww_}, opt___] := Block[{nn, mm, a, c, fnew, wwnew, wnew, qq, m, \[Alpha], q, s2, prec}, \[IndentingNewLine]{prec} = \({PrecisionGoal} /. {opt}\) /. Options[NUFourier]; \[IndentingNewLine]If[prec === Automatic, prec = $MachinePrecision - 11]; \[IndentingNewLine]nn = Length[f]; \n\ \ \ \ \ \ \ nnnew = Length[w]; \[IndentingNewLine]If[nn == nnnew, , Message[NUFourier::incsh]; Break[]]; \ \[IndentingNewLine]If[\((Max[w] - Min[w])\) \((Max[ww] - Min[ww])\) \[LessEqual] \ 20\ nn, , Message[NUFourier::warn]]; \[IndentingNewLine]mm = Length[ ww]; \[IndentingNewLine]If[\((\(nn\^\(1 - 5\/8\)\) mm\^\(5\/8\) < in[prec])\) || \((nn \[LessEqual] 40)\), Table[\[Sum]\+\(k = 0\)\%\(nn - 1\)f[\([k + 1]\)] E\^\(I\ \[Pi]\ \ w[\([k + 1]\)]\ \ ww[\([j]\)]\), {j, 1, mm}], \[IndentingNewLine]a = \(\((w // First)\) + \((w // \ Last)\)\)\/2; \[IndentingNewLine]c = \(\((ww // First)\) + \((ww // Last)\)\)\ \/2; \[IndentingNewLine]fnew = Table[f[\([k + 1]\)]\ E\^\(I\ \[Pi]\ \ w[\([k + 1]\)]\ \ c\), {k, 0, nn - 1}]; \[IndentingNewLine]wwnew = \((ww - c)\) \((\((w // Last)\) - \((w // First)\))\); \[IndentingNewLine]wnew = \((w - a)\)/\((\((w // Last)\) - \((w // First)\))\); \[IndentingNewLine]qq = \ Ceiling[\((wwnew // Last)\)]; \[IndentingNewLine]m = Ceiling[1.7 + 4\/\(prec + 1\)]; \[IndentingNewLine]\[Alpha] = \(m \ \((Log[2] 2\^\(4 - 1.5 prec\) + \ Log[10]\ prec)\)\)\/\(m - 1\); \ \[IndentingNewLine]q = 2\ prec; \[IndentingNewLine]s2 = pe[\[Alpha], {fnew, wnew}, q, m, qq]; \[IndentingNewLine]Table[\(E\^\(I\ \[Pi]\ \ a\ \ \((ww[\([j]\)] - c)\)\)\) E\^\(\[Alpha] \((wwnew[\([j]\)]\/\(2\ m\ qq\))\)\^2\), {j, 1, mm}]\ \ superA2[\(\(\ \)\(wwnew\)\)\/\(\(\ \)\(m\ \ qq\)\), nul[s2, 1.8], prec]]\[IndentingNewLine]];\), "\[IndentingNewLine]", \ \(End[];\), "\n", \(EndPackage[];\)}], "Input"] }, Open ]], Cell[CellGroupData[{ Cell[TextData[StyleBox["Introduction and implementation Notes ", FontColor->RGBColor[0.500008, 0, 0.500008]]], "Section"], Cell[BoxData[ RowBox[{ StyleBox["The", FontFamily->"Courier New"], StyleBox[" ", FontFamily->"Courier New"], StyleBox["package", FontFamily->"Courier New"], StyleBox[" ", FontFamily->"Courier New"], StyleBox["NUFourier", FontFamily->"Courier New", FontWeight->"Bold"], StyleBox[" ", FontFamily->"Courier New"], StyleBox["calculates", FontFamily->"Courier New"], StyleBox[" ", FontFamily->"Courier New"], StyleBox["the", FontFamily->"Courier New"], StyleBox[" ", FontFamily->"Courier New"], StyleBox["list", FontFamily->"Courier New"]}]], "Text"], Cell[BoxData[ RowBox[{ StyleBox[\(\[Sum]\+\(k = 1\)\%N\( f\_k\) E\^\(I\ \[Pi]\ \ \(t\_k\) w\_j\)\), FontSize->18], ",", " ", \(j = 1\), ",", "2", ",", "..", ",", \(M\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \((1)\)\)}]], "Input", TextAlignment->Center, TextJustification->0], Cell[TextData[{ StyleBox["for given complex valued list f={", FontFamily->"Courier New"], Cell[BoxData[ \(f\_k\)], FontFamily->"Courier New"], StyleBox["},real list t={", FontFamily->"Courier New"], Cell[BoxData[ \(t\_k\)], FontFamily->"Courier New"], StyleBox["}(k=1,2,..,N) and real list w={", FontFamily->"Courier New"], Cell[BoxData[ SuperscriptBox[\(w\_k\), Cell[""]]], FontFamily->"Courier New"], StyleBox["}(k=1,2,..,M). The fast calculation of this Fourier Transform on \ (in general)nonuniform grids is one of the important problems in applied \ mathematics.It is now central to many areas, notable spectral analysis in \ signal processing when the input data is not uniformly spaced,as well as for \ mathematical sources of the computer tomography. There are many papers of \ known autors devoted to fast solution of this problem (see [1]). In [2] it \ was solved on the base of the Gaussian Bell function but the technique of \ the precision providing was not properly developed. The current algorithm \ NUFourier[f,{t,w}] is based on the paper[3] which provides both fast \ calculation and about exact required precision for the sum (1).", FontFamily->"Courier New"], "\n ", StyleBox["\n ", FontWeight->"Bold"], StyleBox[" ", FontSize->14, FontWeight->"Bold"], StyleBox[" References", FontFamily->"Courier New", FontSize->14, FontWeight->"Bold"], StyleBox["\n[1] A.F.Ware. Fast Fourier Transforms for Irregularly Spaced \ Data, SIAM Review, vol 40,No 4,1998,pp.838-856.\n[2] A.Dutt,V.Rokhlin,Fast \ Fourier Transforms for Nonequispaced Data,Siam J.Sci.Comput.,vol 14,No \ 6,1993, pp.1368-1393.\n[3] A. Nersessian, Quasiexponential Function and \ Fourier Quasitransforms,Doklady NAN Armenii (Reports of the National Academy \ of Sciences of Armenia), vol 101,No 1,2001,pp.5-11.", FontFamily->"Courier New"] }], "Text", TextAlignment->Left, TextJustification->1], Cell[TextData[{ StyleBox["Implementation notes ", FontSize->16, FontWeight->"Bold"], StyleBox["(see above formula (", "TI", FontSize->14, FontVariations->{"CompatibilityType"->0}], StyleBox["1) )", "TI", FontSize->14, FontSlant->"Plain", FontVariations->{"CompatibilityType"->0}] }], "Text"], Cell[TextData[{ StyleBox["\[FilledSmallSquare]", FontFamily->"Courier New"], StyleBox["NUFourier[", FontFamily->"Courier New", FontWeight->"Bold"], StyleBox["expr,{list1,list2}", FontFamily->"Courier New", FontWeight->"Bold", FontSlant->"Italic"], StyleBox["] ", FontFamily->"Courier New", FontWeight->"Bold"], StyleBox["gives an approximate Discrete Fourier Transform of the ", FontFamily->"Courier New"], StyleBox["expr ", "TI", FontFamily->"Courier New", FontVariations->{"CompatibilityType"->0}], StyleBox[" on the general type nonequally spaced real grid ", "TI", FontFamily->"Courier New", FontSlant->"Plain", FontVariations->{"CompatibilityType"->0}], StyleBox["list2", "TI", FontFamily->"Courier New", FontVariations->{"CompatibilityType"->0}], StyleBox[" when the initial Fourier nodes correspond the general type \ nonequally spaced real grid ", "TI", FontFamily->"Courier New", FontSlant->"Plain", FontVariations->{"CompatibilityType"->0}], StyleBox["list2 ", "TI", FontFamily->"Courier New", FontVariations->{"CompatibilityType"->0}], StyleBox[" for ", "TI", FontFamily->"Courier New", FontSlant->"Plain", FontVariations->{"CompatibilityType"->0}], StyleBox["f=expr, t=list1 and w=list2", "TI", FontFamily->"Courier New", FontVariations->{"CompatibilityType"->0}], StyleBox[").", "TI", FontFamily->"Courier New", FontSlant->"Plain", FontVariations->{"CompatibilityType"->0}], StyleBox["\n\[FilledSmallSquare]", FontFamily->"Courier New"], StyleBox["NUFourier", FontFamily->"Courier New", FontWeight->"Bold"], StyleBox[" ", "MR", FontFamily->"Courier New", FontSlant->"Italic"], StyleBox["has the option ", "MR", FontFamily->"Courier New", FontVariations->{"CompatibilityType"->0}], Cell[BoxData[ \(\(\(PrecisionGoal\)\(\[Rule]\)\)\)], FontFamily->"Courier New"], StyleBox["p with default setting ", "MR", FontFamily->"Courier New", FontVariations->{"CompatibilityType"->0}], Cell[BoxData[ \(p = $MachinePrecision - 11\)], FontFamily->"Courier New"], StyleBox[".\n", "MR", FontFamily->"Courier New", FontVariations->{"CompatibilityType"->0}], StyleBox["\[FilledSmallSquare]T", FontFamily->"Courier New"], StyleBox["he option ", "MR", FontFamily->"Courier New", FontVariations->{"CompatibilityType"->0}], Cell[BoxData[ \(PrecisionGoal\)], FontFamily->"Courier New"], StyleBox[" corresponds to relative ", "MR", FontFamily->"Courier New", FontVariations->{"CompatibilityType"->0}], Cell[BoxData[ \(TraditionalForm\`L\_2\)], FontFamily->"Courier New"], StyleBox["-error of the output list.\n\[FilledSmallSquare]If N M is not big \ (", FontFamily->"Courier New"], Cell[BoxData[ \( \[LessEqual] \)], FontFamily->"Courier New"], StyleBox[" about ", FontFamily->"Courier New"], Cell[BoxData[ \(TraditionalForm\`100\^2\)], FontFamily->"Courier New"], StyleBox[" ) or only N is not big (", FontFamily->"Courier New"], Cell[BoxData[ \(\(\(N\)\(\[LessEqual]\)\)\)], FontFamily->"Courier New"], StyleBox["40) ", FontFamily->"Courier New"], StyleBox["NUFourier", FontFamily->"Courier New", FontWeight->"Bold"], StyleBox[" works by the direct calculation of the sum (1). Otherwise the \ wavelet technique is used.\n\[FilledSmallSquare]", FontFamily->"Courier New"], StyleBox["NUFourier", FontFamily->"Courier New", FontWeight->"Bold"], StyleBox[" ", "MR", FontFamily->"Courier New", FontSlant->"Italic"], StyleBox["works more faster if ", "MR", FontFamily->"Courier New", FontVariations->{"CompatibilityType"->0}], Cell[BoxData[ \(M >> N\)], FontFamily->"Courier New"], StyleBox[".\n\[FilledSmallSquare]The theoretical complexity of the direct \ calculation of the sum (1) is about 2 N\[Times]M arithmetic operations. The \ cost of the ", FontFamily->"Courier New"], StyleBox["NUFourier", FontFamily->"Courier New", FontWeight->"Bold"], StyleBox[" ", "MR", FontFamily->"Courier New", FontSlant->"Italic"], StyleBox[" is proportional to N(LogN+p) for PrecisionGoal->p. ", "MR", FontFamily->"Courier New", FontVariations->{"CompatibilityType"->0}], StyleBox["\n\[FilledSmallSquare]", FontFamily->"Courier New"], " ", StyleBox["NUFourier", FontFamily->"Courier New", FontWeight->"Bold"], StyleBox[" works best if ", FontFamily->"Courier New"], StyleBox[" ", "MR", FontFamily->"Courier New", FontVariations->{"CompatibilityType"->0}], Cell[BoxData[ \(TraditionalForm\`N >> 1, M >> 1\)], FontFamily->"Courier New"], ", ", StyleBox[" ", FontFamily->"Courier New"], Cell[BoxData[ \(M > N\ \ /10\)]], StyleBox[" and ", FontFamily->"Courier New"], Cell[BoxData[ \(\((max {t\_k} - min {t\_k})\) \((max {w\_k} - min {w\_k})\) \[LessEqual] 20\ N\)], FontFamily->"Courier New"] }], "Text", CellMargins->{{Inherited, 57}, {Inherited, Inherited}}, TextAlignment->Left, TextJustification->1, CellTags->{"S0.1200", "FourierTransform"}] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ StyleBox["Demonstration of the package", FontWeight->"Bold", FontColor->RGBColor[0.250004, 0.500008, 0.500008]], StyleBox[" ", FontWeight->"Bold", FontColor->RGBColor[1, 0, 1]] }], "Section"], Cell[BoxData[ StyleBox[\(All\ examples\ were\ solved\ on\ the\ computer\n PENTIUM\ 4, 1.5\ GHz, 512\ RAM\), FontSize->16, FontColor->RGBColor[0, 0, 0.500008]]], "Input", TextAlignment->Center, TextJustification->0], Cell[TextData[{ StyleBox[" Here we calculate the sum ", FontFamily->"Courier New"], Cell[BoxData[ \(\[Sum]\+\(k = 1\)\%N\( f\_k\) E\^\(I\ \[Pi]\ \(t\_k\) \(\(w\)\(\ \)\)\_j\)\)], FontFamily->"Courier New"], StyleBox[", ", FontFamily->"Courier New"], Cell[BoxData[ \(j = 1, \(\(...\) \(2\) \(N\)\)\)], FontFamily->"Courier New"], StyleBox[" for a random complex list {", FontFamily->"Courier New"], Cell[BoxData[ \(f\_k\)], FontFamily->"Courier New"], StyleBox["} and random real lists {", FontFamily->"Courier New"], Cell[BoxData[ \(t\_k\)], FontFamily->"Courier New"], StyleBox["} and {", FontFamily->"Courier New"], Cell[BoxData[ \(w\_j\)], FontFamily->"Courier New"], StyleBox["} and compare the times of direct evaluation with the time of \ program NUFourier[] when the last is working with default ", FontFamily->"Courier New"], Cell[BoxData[ \(precision = 5\)], FontFamily->"Courier New"], StyleBox[". ", FontFamily->"Courier New"] }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Do[Block[{nn = 2^y, mm = 2\ nn, t, f, x, s1, s2}, \[IndentingNewLine]Print["\<**** M->\>", mm, "\<****N->\>", nn]; \[IndentingNewLine]t = Sort[Table[\ Random[Real, {0, 2}], {nn}]]; \[IndentingNewLine]f = Table[2 Random[ Complex, {\(-1\) - I, 1 + 2 I}], {nn}]; \[IndentingNewLine]x = Sort[Table[ Random[Real, {0, mm}], {mm}]]; \[IndentingNewLine]{time1, s2} = NUFourier[f, {t, x}] // Timing; \[IndentingNewLine]\ {time2, s1} = Table[\[Sum]\+\(k = 0\)\%\(nn - 1\)f[\([k + 1]\)] E\^\(I\ \[Pi]\ \ t[\([k + 1]\)]\ \ x[\([j]\)]\), {j, 1, mm}] // Timing; \[IndentingNewLine]Print["\{direct,fast,direct/\ fast}->\>", {time2, time1, time2/time1}]; \[IndentingNewLine]Print[\*"\"\\>\"", Sqrt[Apply[Plus, Abs[s1 - s2]\^2]]/ Sqrt[Apply[Plus, Abs[s1]^2]]]\[IndentingNewLine]], {y, 4, 24}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]32\[InvisibleSpace]"****N->"\[InvisibleSpace]16\), SequenceForm[ "**** M->", 32, "****N->", 16], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{direct,fast,direct/fast}->"\[InvisibleSpace]{\ 0.01999999999999602`\ Second, 0.01999999999999602`\ Second, 1.`}\), SequenceForm[ "Time->{direct,fast,direct/fast}->", { Times[ .019999999999996021, Second], Times[ .019999999999996021, Second], 1.0}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Relative \!\(L\_2\)-error->"\[InvisibleSpace]0.`\), SequenceForm[ "Relative \!\(L\_2\)-error->", 0.0], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]64\[InvisibleSpace]"****N->"\[InvisibleSpace]32\), SequenceForm[ "**** M->", 64, "****N->", 32], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{direct,fast,direct/fast}->"\[InvisibleSpace]{\ 0.060000000000002274`\ Second, 0.04999999999999716`\ Second, 1.2000000000001136`}\), SequenceForm[ "Time->{direct,fast,direct/fast}->", { Times[ .060000000000002274, Second], Times[ .049999999999997158, Second], 1.2000000000001136}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Relative \!\(L\_2\)-error->"\[InvisibleSpace]0.`\), SequenceForm[ "Relative \!\(L\_2\)-error->", 0.0], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]128\[InvisibleSpace]"****N->"\[InvisibleSpace]64\), SequenceForm[ "**** M->", 128, "****N->", 64], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{direct,fast,direct/fast}->"\[InvisibleSpace]{\ 0.23000000000000398`\ Second, 0.15000000000000568`\ Second, 1.5333333333333017`}\), SequenceForm[ "Time->{direct,fast,direct/fast}->", { Times[ .23000000000000398, Second], Times[ .15000000000000568, Second], 1.5333333333333017}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Relative \ \!\(L\_2\)-error->"\[InvisibleSpace]4.065390720949422`*^-6\), SequenceForm[ "Relative \!\(L\_2\)-error->", .40653907209494217*^-5], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]256\[InvisibleSpace]"****N->"\[InvisibleSpace]128\), SequenceForm[ "**** M->", 256, "****N->", 128], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{direct,fast,direct/fast}->"\[InvisibleSpace]{\ 0.13000000000000966`\ Second, 0.2809999999999917`\ Second, 0.4626334519573434`}\), SequenceForm[ "Time->{direct,fast,direct/fast}->", { Times[ .13000000000000966, Second], Times[ .2809999999999917, Second], .4626334519573434}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Relative \ \!\(L\_2\)-error->"\[InvisibleSpace]3.4384406741638064`*^-6\), SequenceForm[ "Relative \!\(L\_2\)-error->", .34384406741638064*^-5], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]512\[InvisibleSpace]"****N->"\[InvisibleSpace]256\), SequenceForm[ "**** M->", 512, "****N->", 256], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{direct,fast,direct/fast}->"\[InvisibleSpace]{\ 0.5210000000000008`\ Second, 0.561000000000007`\ Second, 0.9286987522281537`}\), SequenceForm[ "Time->{direct,fast,direct/fast}->", { Times[ .5210000000000008, Second], Times[ .56100000000000705, Second], .92869875222815368}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Relative \ \!\(L\_2\)-error->"\[InvisibleSpace]3.593302665906493`*^-6\), SequenceForm[ "Relative \!\(L\_2\)-error->", .35933026659064932*^-5], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]1024\[InvisibleSpace]"****N->"\[InvisibleSpace]512\), SequenceForm[ "**** M->", 1024, "****N->", 512], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{direct,fast,direct/fast}->"\[InvisibleSpace]{\ 2.0529999999999973`\ Second, 1.090999999999994`\ Second, 1.8817598533455624`}\), SequenceForm[ "Time->{direct,fast,direct/fast}->", { Times[ 2.0529999999999973, Second], Times[ 1.090999999999994, Second], 1.8817598533455624}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Relative \ \!\(L\_2\)-error->"\[InvisibleSpace]4.010840342542333`*^-6\), SequenceForm[ "Relative \!\(L\_2\)-error->", .4010840342542333*^-5], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]2048\[InvisibleSpace]"****N->"\[InvisibleSpace]1024\), SequenceForm[ "**** M->", 2048, "****N->", 1024], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{direct,fast,direct/fast}->"\[InvisibleSpace]{\ 8.141999999999996`\ Second, 2.1230000000000047`\ Second, 3.8351389543099286`}\), SequenceForm[ "Time->{direct,fast,direct/fast}->", { Times[ 8.1419999999999959, Second], Times[ 2.1230000000000047, Second], 3.8351389543099286}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Relative \ \!\(L\_2\)-error->"\[InvisibleSpace]3.959691132141586`*^-6\), SequenceForm[ "Relative \!\(L\_2\)-error->", .39596911321415858*^-5], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]4096\[InvisibleSpace]"****N->"\[InvisibleSpace]2048\), SequenceForm[ "**** M->", 4096, "****N->", 2048], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{direct,fast,direct/fast}->"\[InvisibleSpace]{\ 32.967`\ Second, 4.116`\ Second, 8.009475218658892`}\), SequenceForm[ "Time->{direct,fast,direct/fast}->", { Times[ 32.966999999999999, Second], Times[ 4.1159999999999997, Second], 8.009475218658892}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Relative \ \!\(L\_2\)-error->"\[InvisibleSpace]3.7060826476976716`*^-6\), SequenceForm[ "Relative \!\(L\_2\)-error->", .37060826476976716*^-5], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]8192\[InvisibleSpace]"****N->"\[InvisibleSpace]4096\), SequenceForm[ "**** M->", 8192, "****N->", 4096], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{direct,fast,direct/fast}->"\[InvisibleSpace]{\ 132.321`\ Second, 8.111000000000018`\ Second, 16.313771421526287`}\), SequenceForm[ "Time->{direct,fast,direct/fast}->", { Times[ 132.321, Second], Times[ 8.1110000000000184, Second], 16.313771421526287}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Relative \ \!\(L\_2\)-error->"\[InvisibleSpace]3.913954341855076`*^-6\), SequenceForm[ "Relative \!\(L\_2\)-error->", .39139543418550759*^-5], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]16384\[InvisibleSpace]"****N->"\[InvisibleSpace]8192\), SequenceForm[ "**** M->", 16384, "****N->", 8192], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{direct,fast,direct/fast}->"\[InvisibleSpace]{\ 534.8489999999999`\ Second, 16.13299999999998`\ Second, 33.152482489307666`}\), SequenceForm[ "Time->{direct,fast,direct/fast}->", { Times[ 534.84899999999993, Second], Times[ 16.132999999999981, Second], 33.152482489307666}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Relative \ \!\(L\_2\)-error->"\[InvisibleSpace]3.910480826349945`*^-6\), SequenceForm[ "Relative \!\(L\_2\)-error->", .39104808263499447*^-5], Editable->False]], "Print"] }, Closed]], Cell[TextData[StyleBox[" Here we calculate the previous sum omly by the \ program NUFourier[] for more big values of N and M", FontFamily->"Courier New"]], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Do[Block[{nn = 2^y, mm = 2\ nn, t, f, x, s1, s2}, \[IndentingNewLine]Print["\<**** M->\>", mm, "\<****N->\>", nn]; \[IndentingNewLine]t = Sort[Table[Random[Real, {0, 2}], {nn}]]; \[IndentingNewLine]f = Table[2 Random[ Complex, {\(-1\) - I, 1 + 2 I}], {nn}]; \[IndentingNewLine]x = Sort[Table[ Random[Real, {0, mm}], {mm}]]; \[IndentingNewLine]{time1, s2} = NUFourier[f, {t, x}] // Timing; \[IndentingNewLine]Print["\{fast}->\>", {time1}];\ \[IndentingNewLine]], {y, 4, 24}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]32\[InvisibleSpace]"****N->"\[InvisibleSpace]16\), SequenceForm[ "**** M->", 32, "****N->", 16], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{fast}->"\[InvisibleSpace]{0.\ 009999999999990905`\ Second}\), SequenceForm[ "Time->{fast}->", { Times[ .0099999999999909051, Second]}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]64\[InvisibleSpace]"****N->"\[InvisibleSpace]32\), SequenceForm[ "**** M->", 64, "****N->", 32], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{fast}->"\[InvisibleSpace]{0.05999999999994543`\ \ Second}\), SequenceForm[ "Time->{fast}->", { Times[ .05999999999994543, Second]}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]128\[InvisibleSpace]"****N->"\[InvisibleSpace]64\), SequenceForm[ "**** M->", 128, "****N->", 64], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{fast}->"\[InvisibleSpace]{0.12000000000011823`\ \ Second}\), SequenceForm[ "Time->{fast}->", { Times[ .12000000000011823, Second]}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]256\[InvisibleSpace]"****N->"\[InvisibleSpace]128\), SequenceForm[ "**** M->", 256, "****N->", 128], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{fast}->"\[InvisibleSpace]{0.23099999999999454`\ \ Second}\), SequenceForm[ "Time->{fast}->", { Times[ .23099999999999454, Second]}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]512\[InvisibleSpace]"****N->"\[InvisibleSpace]256\), SequenceForm[ "**** M->", 512, "****N->", 256], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{fast}->"\[InvisibleSpace]{0.4800000000000182`\ \ Second}\), SequenceForm[ "Time->{fast}->", { Times[ .48000000000001819, Second]}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]1024\[InvisibleSpace]"****N->"\[InvisibleSpace]512\), SequenceForm[ "**** M->", 1024, "****N->", 512], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{fast}->"\[InvisibleSpace]{1.0019999999999527`\ \ Second}\), SequenceForm[ "Time->{fast}->", { Times[ 1.0019999999999527, Second]}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]2048\[InvisibleSpace]"****N->"\[InvisibleSpace]1024\), SequenceForm[ "**** M->", 2048, "****N->", 1024], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{fast}->"\[InvisibleSpace]{1.9629999999999654`\ \ Second}\), SequenceForm[ "Time->{fast}->", { Times[ 1.9629999999999654, Second]}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]4096\[InvisibleSpace]"****N->"\[InvisibleSpace]2048\), SequenceForm[ "**** M->", 4096, "****N->", 2048], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{fast}->"\[InvisibleSpace]{3.884999999999991`\ \ Second}\), SequenceForm[ "Time->{fast}->", { Times[ 3.8849999999999909, Second]}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]8192\[InvisibleSpace]"****N->"\[InvisibleSpace]4096\), SequenceForm[ "**** M->", 8192, "****N->", 4096], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{fast}->"\[InvisibleSpace]{8.231999999999971`\ \ Second}\), SequenceForm[ "Time->{fast}->", { Times[ 8.2319999999999709, Second]}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]16384\[InvisibleSpace]"****N->"\[InvisibleSpace]8192\), SequenceForm[ "**** M->", 16384, "****N->", 8192], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{fast}->"\[InvisibleSpace]{16.923999999999978`\ \ Second}\), SequenceForm[ "Time->{fast}->", { Times[ 16.923999999999978, Second]}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]32768\[InvisibleSpace]"****N->"\[InvisibleSpace]16384\), SequenceForm[ "**** M->", 32768, "****N->", 16384], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{fast}->"\[InvisibleSpace]{34.21900000000005`\ \ Second}\), SequenceForm[ "Time->{fast}->", { Times[ 34.219000000000051, Second]}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]65536\[InvisibleSpace]"****N->"\[InvisibleSpace]32768\), SequenceForm[ "**** M->", 65536, "****N->", 32768], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{fast}->"\[InvisibleSpace]{70.98199999999997`\ \ Second}\), SequenceForm[ "Time->{fast}->", { Times[ 70.981999999999971, Second]}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("**** \ M->"\[InvisibleSpace]131072\[InvisibleSpace]"****N->"\[InvisibleSpace]65536\), SequenceForm[ "**** M->", 131072, "****N->", 65536], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Time->{fast}->"\[InvisibleSpace]{149.10400000000004`\ \ Second}\), SequenceForm[ "Time->{fast}->", { Times[ 149.10400000000004, Second]}], Editable->False]], "Print"] }, Closed]], Cell[BoxData[ StyleBox["Conclusion", FontSize->18, FontColor->RGBColor[1, 0, 0]]], "Input"], Cell[TextData[{ StyleBox[" From this and several other experiments we can conclude that if \ N and M are growing together then the time of \n", FontFamily->"Courier New"], StyleBox["NUFourier", FontFamily->"Courier New", FontWeight->"Bold"], StyleBox[" (in the last resort for large values of N and M) is much less \ than the time of direct calculation of the sum (1).", FontFamily->"Courier New"] }], "Text"] }, Closed]] }, Open ]] }, FrontEndVersion->"4.1 for Microsoft Windows", ScreenRectangle->{{0, 1024}, {0, 695}}, AutoGeneratedPackage->None, WindowToolbars->"EditBar", WindowSize->{885, 658}, WindowMargins->{{5, Automatic}, {Automatic, 1}}, PrintingCopies->1, PrintingPageRange->{Automatic, Automatic} ] (******************************************************************* Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. *******************************************************************) (*CellTagsOutline CellTagsIndex->{ "S0.1200"->{ Cell[27542, 598, 5250, 159, 231, "Text", CellTags->{"S0.1200", "FourierTransform"}]}, "FourierTransform"->{ Cell[27542, 598, 5250, 159, 231, "Text", CellTags->{"S0.1200", "FourierTransform"}]} } *) (*CellTagsIndex CellTagsIndex->{ {"S0.1200", 51436, 1275}, {"FourierTransform", 51556, 1278} } *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[1727, 52, 244, 6, 97, "Subsubtitle"], Cell[CellGroupData[{ Cell[1996, 62, 242, 9, 81, "Section"], Cell[2241, 73, 21701, 419, 3212, "Input"] }, Open ]], Cell[CellGroupData[{ Cell[23979, 497, 123, 1, 59, "Section"], Cell[24105, 500, 721, 24, 31, "Text"], Cell[24829, 526, 384, 9, 67, "Input"], Cell[25216, 537, 1994, 46, 306, "Text"], Cell[27213, 585, 326, 11, 37, "Text"], Cell[27542, 598, 5250, 159, 231, "Text", CellTags->{"S0.1200", "FourierTransform"}] }, Closed]], Cell[CellGroupData[{ Cell[32829, 762, 228, 7, 39, "Section"], Cell[33060, 771, 240, 6, 55, "Input"], Cell[33303, 779, 1080, 35, 73, "Text"], Cell[CellGroupData[{ Cell[34408, 818, 1067, 20, 238, "Input"], Cell[35478, 840, 203, 4, 21, "Print"], Cell[35684, 846, 351, 6, 21, "Print"], Cell[36038, 854, 181, 3, 21, "Print"], Cell[36222, 859, 203, 4, 21, "Print"], Cell[36428, 865, 394, 7, 21, "Print"], Cell[36825, 874, 181, 3, 21, "Print"], Cell[37009, 879, 205, 4, 21, "Print"], Cell[37217, 885, 391, 7, 21, "Print"], Cell[37611, 894, 221, 4, 21, "Print"], Cell[37835, 900, 207, 4, 21, "Print"], Cell[38045, 906, 388, 7, 21, "Print"], Cell[38436, 915, 222, 4, 21, "Print"], Cell[38661, 921, 207, 4, 21, "Print"], Cell[38871, 927, 387, 7, 21, "Print"], Cell[39261, 936, 221, 4, 21, "Print"], Cell[39485, 942, 209, 4, 21, "Print"], Cell[39697, 948, 387, 7, 21, "Print"], Cell[40087, 957, 220, 4, 21, "Print"], Cell[40310, 963, 211, 4, 21, "Print"], Cell[40524, 969, 388, 7, 21, "Print"], Cell[40915, 978, 221, 4, 21, "Print"], Cell[41139, 984, 211, 4, 21, "Print"], Cell[41353, 990, 351, 6, 21, "Print"], Cell[41707, 998, 222, 4, 21, "Print"], Cell[41932, 1004, 211, 4, 21, "Print"], Cell[42146, 1010, 355, 6, 21, "Print"], Cell[42504, 1018, 221, 4, 21, "Print"], Cell[42728, 1024, 213, 4, 21, "Print"], Cell[42944, 1030, 387, 7, 21, "Print"], Cell[43334, 1039, 221, 4, 21, "Print"] }, Closed]], Cell[43570, 1046, 165, 2, 30, "Text"], Cell[CellGroupData[{ Cell[43760, 1052, 643, 12, 170, "Input"], Cell[44406, 1066, 203, 4, 21, "Print"], Cell[44612, 1072, 229, 5, 21, "Print"], Cell[44844, 1079, 203, 4, 21, "Print"], Cell[45050, 1085, 226, 5, 21, "Print"], Cell[45279, 1092, 205, 4, 21, "Print"], Cell[45487, 1098, 226, 5, 21, "Print"], Cell[45716, 1105, 207, 4, 21, "Print"], Cell[45926, 1111, 226, 5, 21, "Print"], Cell[46155, 1118, 207, 4, 21, "Print"], Cell[46365, 1124, 225, 5, 21, "Print"], Cell[46593, 1131, 209, 4, 21, "Print"], Cell[46805, 1137, 225, 5, 21, "Print"], Cell[47033, 1144, 211, 4, 21, "Print"], Cell[47247, 1150, 225, 5, 21, "Print"], Cell[47475, 1157, 211, 4, 21, "Print"], Cell[47689, 1163, 224, 5, 21, "Print"], Cell[47916, 1170, 211, 4, 21, "Print"], Cell[48130, 1176, 224, 5, 21, "Print"], Cell[48357, 1183, 213, 4, 21, "Print"], Cell[48573, 1189, 225, 5, 21, "Print"], Cell[48801, 1196, 215, 4, 21, "Print"], Cell[49019, 1202, 224, 5, 21, "Print"], Cell[49246, 1209, 215, 4, 21, "Print"], Cell[49464, 1215, 224, 5, 21, "Print"], Cell[49691, 1222, 224, 5, 21, "Print"], Cell[49918, 1229, 225, 5, 21, "Print"] }, Closed]], Cell[50158, 1237, 107, 3, 32, "Input"], Cell[50268, 1242, 432, 10, 72, "Text"] }, Closed]] }, Open ]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)