(************** 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[ 38405, 1208]*)
(*NotebookOutlinePosition[ 39096, 1232]*)
(* CellTagsIndexPosition[ 39052, 1228]*)
(*WindowFrame->Normal*)
Notebook[{
Cell[CellGroupData[{
Cell["Effective Real Root Isolation Using Continued Fractions", "Title"],
Cell["Alkiviadis G. Akritas", "Author"],
Cell["\<\
University of Thessaly, Department of Computer and Communication \
Engineering, GR-38221 Volos, Greece\
\>", "Address"],
Cell[CellGroupData[{
Cell["Adam W. Strzebonski", "Author"],
Cell["\<\
Wolfram Research, Inc., 100 Trade Center Drive, Champaign, IL \
61820, USA\
\>", "Address"],
Cell[TextData[{
"Recent progress in polynomial elimination has rendered the computation of \
the real roots of ill-conditioned polynomials of high degree > 1000 with huge \
coefficients (several thousand digits) a critical operation in computer \
algebra. To rise to the occasion, the only method-candidate that has been \
considered by various authors for modification and improvement has been the \
Collins-Akritas ",
StyleBox["bisection",
FontSlant->"Italic"],
" method [CA1976]. The most recent example is a preprint [RZ2002], where \
the authors try to present\n\n",
StyleBox["...all the known algorithms in a unified framework. Using that \
framework, a new algorithm is presented, which is optimal in terms of memory \
usage and as fast as both Collins and Akritas' algorithm and Krandick \
variant... \n",
FontSlant->"Italic"],
"\nHowever, the authors of that preprint failed to include our own ",
StyleBox["continued fractions",
FontSlant->"Italic"],
" method [ABS1994] in their consideration. Developed in 1994 for \
implementation in the computer algebra system ",
StyleBox["Mathematica",
FontSlant->"Italic"],
", our method is based on Vincent's theorem [V1836]-extended by Uspensky \
[U1948], to guarantee that the process terminates, and modified by one of us \
[Akr1978]-and is amply described in [Akr1980], [Akr1989] and [ABS1994]. \
Experimentation with the data presented in [RZ2002] showed that, with respect \
to time, our continued fractions method is by far superior to the one \
presented in the most recent preprint, whereas the two are about equal with \
respect to space. Moreover, it should be kept in mind that there is only one \
unifying principle, to wit ",
StyleBox["continued fractions",
FontSlant->"Italic"],
", which in the Collins-Akritas bisection method are ",
StyleBox["indirectly",
FontSlant->"Italic"],
" computed from the intervals. Therefore, our method ",
StyleBox["is",
FontSlant->"Italic"],
" the unifying framework."
}], "Abstract"],
Cell[CellGroupData[{
Cell["Introduction-or Paying tribute to Vincent!", "Section"],
Cell["\<\
Vincent's theorem, extended to guarantee termination, can be stated \
as follows:\
\>", "Text"],
Cell[TextData[{
StyleBox["Vincent's Theorem (1836).",
FontWeight->"Bold"],
" Let ",
Cell[BoxData[
\(TraditionalForm\`p(x) = 0\)]],
" be a polynomial equation of degree ",
Cell[BoxData[
\(TraditionalForm\`n > 1\)]],
", with rational coefficients and without multiple roots, and let ",
Cell[BoxData[
\(TraditionalForm\`\[CapitalDelta] > 0\)]],
" be the smallest distance between any two of its roots. Let ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
" be the smallest index such that"
}], "Text"],
Cell[BoxData[
\(\(F\_\(m - 1\)\) \[CapitalDelta]\/2 >
1, \(F\_\(m - 1\)\) \(F\_m\) \[CapitalDelta] >
1 + 1\/\[Epsilon]\_n, \)], "DisplayFormula"],
Cell[TextData[{
"where ",
Cell[BoxData[
\(TraditionalForm\`F\_k\)]],
" is the ",
Cell[BoxData[
\(TraditionalForm\`k\)]],
"-th member of the Fibonacci sequence ",
Cell[BoxData[
\(TraditionalForm\`1, 1, 2, 3, 5, 8, 13, 21, \[Ellipsis]\)]],
" and"
}], "Text"],
Cell[BoxData[
\(\[Epsilon]\_n = \((1 + 1\/n)\)\^\(1\/\(n - 1\)\) -
1\)], "DisplayFormula"],
Cell[TextData[{
"Let ",
Cell[BoxData[
\(TraditionalForm\`a\_1\)]],
" be an arbitrary nonnegative integer, and let ",
Cell[BoxData[
\(TraditionalForm\`a\_2, \[Ellipsis], a\_m\)]],
" be arbitrary positive integers. Then the substitution"
}], "Text"],
Cell[BoxData[
\(x\[LongLeftArrow]a\_1 +
1\/\(a\_2 + 1\/\(\[DescendingEllipsis] + 1\/\(a\_m + 1\/\[Xi]\)\)\)\)], \
"DisplayFormula"],
Cell[TextData[{
"transforms the equation ",
Cell[BoxData[
\(TraditionalForm\`p(x) = 0\)]],
" into the equation ",
Cell[BoxData[
\(TraditionalForm\`p(\[Xi]) = 0\)]],
", which has not more than one sign variation."
}], "Text"],
Cell[TextData[{
"This theorem can be used to isolate the positive roots of a polynomial \
equations ",
Cell[BoxData[
\(TraditionalForm\`p(x) = 0\)]],
". For the negative roots we simply replace ",
Cell[BoxData[
\(TraditionalForm\`x\[LongLeftArrow]\(-x\)\)]],
" and repeat the process. The substitution of ",
Cell[BoxData[
\(TraditionalForm\`x\)]],
", in ",
Cell[BoxData[
\(TraditionalForm\`p(x) = 0\)]],
", by the continued fraction shown in Vincent's theorem results in all \
roots being clustered around -1 within a circle of radius ",
Cell[BoxData[
\(TraditionalForm\`\[Epsilon]\_n\)]],
"."
}], "Text"],
Cell["\<\
Vincent used the weaker version of his theorem (that is, without \
the terminating condition) to isolate the real roots of polynomial equations \
with rational coefficients [V1836]. In his paper of 1836 he presents several \
examples to demonstrate the concepts involved.\
\>", "Text"],
Cell["\<\
Note that Vincent's method appeared several years after Sturm's \
method for isolating the real roots. Due to Sturm's fame and his priority, \
Vincent's method was almost totally forgotten.\
\>", "Text"],
Cell[TextData[{
"In 1975-76 Akritas rediscovered Vincent's theorem in Uspensky's book. \
Without thoroughly studying the historical background, Collins and Akritas-in \
their paper [CA1976]-erroneously named the method they developed, their \
method, the ",
StyleBox["modified Uspensky's method",
FontSlant->"Italic"],
". They were misled by Uspensky's claim (in the preface of his book \
[U1948]) that he himself had invented Vincent's method."
}], "Text"],
Cell["\<\
The mistake was caught by Akritas in his Ph.D.Thesis [Akr1978b] and \
was subsequently announced in [Akr1982], [Akr1984] and [Akr1989]. The gist of \
the matter is that Uspensky was not aware of the Budan's theorem; its \
statement is as follows:\
\>", "Text"],
Cell[TextData[{
StyleBox["Budan's Theorem (1807). ",
FontWeight->"Bold"],
"If in an equation in ",
Cell[BoxData[
\(TraditionalForm\`x\)]],
" of degree ",
Cell[BoxData[
\(TraditionalForm\`n > 0\)]],
", ",
Cell[BoxData[
\(TraditionalForm\`p(x) = 0\)]],
" we make two substitutions, ",
Cell[BoxData[
\(TraditionalForm\`x\[LongLeftArrow]\[Alpha] + x'\)]],
" and x\[LongLeftArrow] ",
Cell[BoxData[
\(TraditionalForm\`\[Beta] + x''\)]],
", where ",
Cell[BoxData[
\(TraditionalForm\`\[Alpha]\)]],
" and ",
Cell[BoxData[
\(TraditionalForm\`\[Beta]\)]],
" are real numbers such that ",
Cell[BoxData[
\(TraditionalForm\`\[Alpha] < \[Beta]\)]],
", then the following hold:"
}], "Text"],
Cell[TextData[{
"(\[Alpha]) The transformed equation in ",
Cell[BoxData[
\(TraditionalForm\`x' = x - \[Alpha]\)]],
" cannot have fewer sign variations than the transformed equation in ",
Cell[BoxData[
\(TraditionalForm\`x'' = x - \[Beta]\)]],
"."
}], "Text"],
Cell[TextData[{
"(\[Beta]) The number of real roots in of the equation ",
Cell[BoxData[
\(TraditionalForm\`p(x) = 0\)]],
", located between ",
Cell[BoxData[
\(TraditionalForm\`\[Alpha]\)]],
" and ",
Cell[BoxData[
\(TraditionalForm\`\[Beta]\)]],
", can never be greater than the number of sign variations lost in the \
sequence of coefficients in passing from the transformed equation in ",
Cell[BoxData[
\(TraditionalForm\`x' = x - \[Alpha]\)]],
" to the transformed equation in ",
Cell[BoxData[
\(TraditionalForm\`x'' = x - \[Beta]\)]],
"."
}], "Text"],
Cell[TextData[{
"(\[Gamma]) When the number of real roots of ",
Cell[BoxData[
\(TraditionalForm\`p(x) = 0\)]],
" located between ",
Cell[BoxData[
\(TraditionalForm\`\[Alpha]\)]],
" and ",
Cell[BoxData[
\(TraditionalForm\`\[Beta]\)]],
" is less than the number of sign variations lost in the sequence of \
coefficients in passing from the transformed equation in ",
Cell[BoxData[
\(TraditionalForm\`x' = x - \[Alpha]\)]],
" to the transformed equation in ",
Cell[BoxData[
\(TraditionalForm\`x'' = x - \[Beta]\)]],
", the difference is an even number."
}], "Text"],
Cell["\<\
Note that Budan's theorem above is almost always confused with the \
one by Fourier on the same subject. It is exclusively Fourier's theorem of \
1820 that appears in the literature under the names \"Fourier\", \"Budan\", \
or \"Budan-Fourier\".\
\>", "Text"],
Cell[TextData[{
"Because of his ignorance of Budan's theorem, Uspensky uses Vincent's \
theorem in the following ",
StyleBox["time consuming",
FontSlant->"Italic"],
" way to compute a partial quotient ",
Cell[BoxData[
\(TraditionalForm\`a\_i\)]],
": after ",
StyleBox["each",
FontSlant->"Italic"],
" translation (Taylor shift) ",
Cell[BoxData[
\(TraditionalForm\`x\[LongLeftArrow]x + 1\)]],
" he has to perform the substitution ",
Cell[BoxData[
\(TraditionalForm\`x\[LongLeftArrow]\(1\/\(x + 1\)\)\)]],
" , to make sure he has not lost any roots in that interval."
}], "Text"],
Cell[TextData[{
"Vincent, on the contrary, being fully aware of Budan's theorem-he actually \
states ",
StyleBox["both",
FontSlant->"Italic"],
" Budan's and Fourier's theorems in his 1836 article-makes only Taylor \
shifts ",
Cell[BoxData[
\(TraditionalForm\`x\[LongLeftArrow]x + 1\)]],
" until he detects a loss in the number of sign variations. ",
StyleBox["Then and only then",
FontSlant->"Italic"],
" does Vincent make the substitution ",
Cell[BoxData[
\(TraditionalForm\`x\[LongLeftArrow]\(1\/\(x + 1\)\)\)]],
" knowing that he has computed a partial quotient ",
Cell[BoxData[
\(TraditionalForm\`a\_i\)]],
". Therefore, what Uspensky did was to take Vincent's method and double its \
computing time."
}], "Text"],
Cell[TextData[{
"With this in mind it is somewhat baffling that the authors in [RZ2002] \
time and again refer to a certain ",
StyleBox["Uspensky's method",
FontSlant->"Italic"],
" and keep referring to the Collins-Akritas method as the ",
StyleBox["modified Uspensky's method",
FontSlant->"Italic"],
". Hopefully this practice will end. It sets a very bad precedent!\n"
}], "Text"],
Cell["\<\
The only problem with Vincent's continued fractions method is that \
it is exponential in the following two ways:\
\>", "Text"],
Cell[TextData[{
"(exp",
Cell[BoxData[
\(TraditionalForm\`\_1\)]],
") in the number of substitutions of the form ",
Cell[BoxData[
\(TraditionalForm\`x\[LongLeftArrow]x + 1\)]],
", which need to be performed in order to compute\na partial quotient ",
Cell[BoxData[
\(TraditionalForm\`a\_i\)]],
", and"
}], "Text"],
Cell[TextData[{
"(exp",
Cell[BoxData[
\(TraditionalForm\`\_2\)]],
") in the growth of the integer coefficients of the polynomials, which are \
obtained after substitutions of the form ",
Cell[BoxData[
\(TraditionalForm\`x\[LongLeftArrow]x + a\_i\)]],
"."
}], "Text"],
Cell["\<\
One can easily create examples where the number of translations \
makes it prohibitive to use. Uspensky realized the problem but failed to \
solve it.\
\>", "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell["Our continued fractions method", "Section"],
Cell["\<\
It was in Akritas' Ph.D.Thesis [Akr1978b] that the exponentiality \
problem of Vincent's continued fractions method was solved; see also \
[Akr1980] and [Akr1989].\
\>", "Text"],
Cell[TextData[{
"To tackle (exp",
Cell[BoxData[
\(TraditionalForm\`\_1\)]],
"), the problem with the number of transformations, Akritas used Cauchy's \
rule for computing a lower bound on the values of the ",
StyleBox["positive",
FontSlant->"Italic"],
" roots of a polynomial equation. That way, instead of performing \
transformations of the form ",
Cell[BoxData[
\(TraditionalForm\`x\[LongLeftArrow]x + 1\)]],
", he performs Taylor shifts of the form ",
Cell[BoxData[
\(TraditionalForm\`x\[LongLeftArrow]x + a\_i\)]],
", where ",
Cell[BoxData[
\(TraditionalForm\`a\_i = floor(nextroots)\)]],
". It should be noted that the substitutions ",
Cell[BoxData[
\(TraditionalForm\`x\[LongLeftArrow]x + 1\)]],
" and ",
Cell[BoxData[
\(TraditionalForm\`x\[LongLeftArrow]x + a\_i\)]],
", for ",
Cell[BoxData[
\(TraditionalForm\`a\_i > 1\)]],
", are executed in about the same amount of time [AD1980]."
}], "Text"],
Cell[TextData[{
"To tackle (exp",
Cell[BoxData[
\(TraditionalForm\`\_2\)]],
"), the problem with the growth of the integer coefficients, Akritas used a \
theorem by Lang and Trotter [LT1972] to justify the claim that ",
Cell[BoxData[
\(TraditionalForm\`a\_i = O(\(||\)\(p(x)\)\( || \_\[Infinity]\))\)]],
" for all ",
Cell[BoxData[
\(TraditionalForm\`i = 1, \[Ellipsis], m\)]],
"; that is, the ",
Cell[BoxData[
\(TraditionalForm\`a\_i\)]],
"s are about as big as the biggest coefficient of the polynomial equation \
whose roots we want to isolate."
}], "Text"],
Cell["The interesting result by Lang and Trotter states that:", "Text"],
Cell[TextData[{
StyleBox["In the continued fraction expansion of almost all numbers, the \
probability that ",
FontSlant->"Italic"],
Cell[BoxData[
\(TraditionalForm\`a\_i\)],
FontSlant->"Italic"],
StyleBox[", the ",
FontSlant->"Italic"],
Cell[BoxData[
\(TraditionalForm\`i\)],
FontSlant->"Italic"],
StyleBox["-th partial quotient, is equal to a positive integer ",
FontSlant->"Italic"],
Cell[BoxData[
\(TraditionalForm\`j\)],
FontSlant->"Italic"],
StyleBox[" is given by ",
FontSlant->"Italic"],
Cell[BoxData[
\(TraditionalForm\`\(log\_2\) \((j + 1)\)\^2\/\(j(j + 2)\)\)],
FontSlant->"Italic"],
StyleBox[".",
FontSlant->"Italic"]
}], "Text"],
Cell[TextData[{
"For almost all numbers, this means that the probability for ",
Cell[BoxData[
\(TraditionalForm\`a\_i = 1\)]],
" is approximately 0.41. Likewise, the probability for ",
Cell[BoxData[
\(TraditionalForm\`a\_i = 1000\)]],
" is approximately ",
Cell[BoxData[
\(TraditionalForm\`1.44\ 10\^\(-6\) \[TildeTilde] 0\)]],
"."
}], "Text"],
Cell["\<\
So, the result by Lang and Trotter tells us, on one hand, that we \
cannot bound the size of the partial quotients and, hence, we cannot control \
the growth of the coefficients. On the other hand, however, due to the fact \
that we use few partial quotients to isolate the roots, this same result \
tells us that the probability of big partial quotients is equal to zero and, \
hence, the claim is well-founded [Akr1989].\
\>", "Text"],
Cell[TextData[{
"Subsequently Akritas, Bocharov and Strzebonski improved the performance of \
continued fraction method for polynomials with large roots by adding a \
substitution ",
Cell[BoxData[
\(TraditionalForm\`x\[LongLeftArrow]a\ x\)]],
" whenever the lower bound ",
Cell[BoxData[
\(TraditionalForm\`a\)]],
" on the values of the positive roots is large. In [ABS1994] they run \
extensive empirical comparison between implementations of the\ncontinued \
fractions method and the Collins-Akritas method, and show that the continued \
fractions method performs significantly faster in all cases except for \
polynomials with all roots real and extermely large, where it is slightly \
slower."
}], "Text"],
Cell[TextData[{
"Our recent improvement is to reduce the memory usage by the continued \
fraction method. We show that the algorithm can be so structured that the \
maximal number of transformed versions of the polynomial that need to be \
stored at any given time is bounded by ",
Cell[BoxData[
\(TraditionalForm\`1 + \(log\_2\) n\)]],
", where ",
Cell[BoxData[
\(TraditionalForm\`n\)]],
" is the degree of the input polynomial. This bound is based on the \
following conjecture, which we have not proven, but which we have extensively \
tested."
}], "Text"],
Cell[TextData[{
"Let ",
Cell[BoxData[
\(TraditionalForm\`f \[Element] \[DoubleStruckCapitalZ][x] \\0\)]],
" be a polynomial of degree ",
Cell[BoxData[
\(TraditionalForm\`n\)]],
", and let ",
Cell[BoxData[
\(TraditionalForm\`sgc(f)\)]],
" denote the number of sign changes in the sequence of nonzero coefficients \
of ",
Cell[BoxData[
\(TraditionalForm\`f\)]],
"."
}], "Text"],
Cell[TextData[StyleBox["Conjecture.",
FontWeight->"Bold"]], "Text"],
Cell[BoxData[
\(sgc \((f \((x + 1)\))\) +
sgc \((\(\((x + 1)\)\^n\) f \((1\/\(x + 1\))\))\) \[LessEqual]
sgc \((f \((x)\))\)\)], "DisplayFormula"],
Cell[CellGroupData[{
Cell["Description of the algorithm", "Subsection"],
Cell[TextData[{
"Let us first introduce the notation used in the algorithm. Let ",
Cell[BoxData[
\(TraditionalForm\`f \[Element] \[DoubleStruckCapitalZ][x] \\0\)]],
". For nonnegative integers ",
Cell[BoxData[
FormBox[
RowBox[{
FormBox["a",
"TraditionalForm"], ",", "b", ",", " ", "c", ",",
" ", \(and\ d\)}], TraditionalForm]]],
" such that ",
Cell[BoxData[
\(TraditionalForm\`a\ d - b\ c \[NotEqual] 0\)]],
", we put"
}], "Text"],
Cell[BoxData[
\(intrv \((a, b, c,
d)\) := \(\[CapitalPhi]\_\(a, b, c,
d\)\) \((\((0, \[Infinity])\))\)\)], "DisplayFormula"],
Cell["where", "Text"],
Cell[BoxData[
\(\(\[CapitalPhi]\_\(a, b, c,
d\)\) : \((0, \[Infinity])\) \[ReverseElement]
x\[LongRightArrow]\(\(a\ x + b\)\/\(c\ x +
d\)\) \[Element] \((0, \[Infinity])\)\)], "DisplayFormula"],
Cell[TextData[{
"and by ",
StyleBox["interval data",
FontSlant->"Italic"],
" we denote a list ",
Cell[BoxData[
\(TraditionalForm\`{a, b, c, d, p, s}\)]],
", where ",
Cell[BoxData[
\(TraditionalForm\`p\)]],
" is a polynomial such that the roots of ",
Cell[BoxData[
\(TraditionalForm\`f\)]],
" in\n ",
Cell[BoxData[
\(TraditionalForm\`intrv(a, b, c, d)\)]],
" are images of positive roots of ",
Cell[BoxData[
\(TraditionalForm\`p\)]],
" through ",
Cell[BoxData[
\(\[CapitalPhi]\_\(a, b, c, d\)\)]],
", and ",
Cell[BoxData[
\(TraditionalForm\`s = sgc(p)\)]],
"."
}], "Text"],
Cell[TextData[{
"The value of parameter ",
Cell[BoxData[
\(TraditionalForm\`\[Alpha]\_0\)]],
" used in step 4 below needs to be chosen empirically. In our \
implementation ",
Cell[BoxData[
\(TraditionalForm\`\[Alpha]\_0 = 16\)]],
". "
}], "Text"],
Cell[TextData[{
StyleBox["Algortihm Continued Fractions.\nInput: ",
FontWeight->"Bold"],
"A squarefree polynomial ",
Cell[BoxData[
\(TraditionalForm\`f \[Element] \[DoubleStruckCapitalZ][x] \\0\)]],
".\n",
StyleBox["Output:",
FontWeight->"Bold"],
" The list ",
StyleBox[" rootlist",
FontSlant->"Italic"],
" of positive roots of ",
Cell[BoxData[
\(TraditionalForm\`f\)]],
"."
}], "Text"],
Cell[TextData[{
"(1) Set ",
StyleBox["rootlist",
FontSlant->"Italic"],
" to an empty list. Compute ",
Cell[BoxData[
\(TraditionalForm\`s \[LeftArrow] sgc\ \((f)\)\)]],
". If ",
Cell[BoxData[
\(TraditionalForm\`s = 0\)]],
" return an empty list. If ",
Cell[BoxData[
\(TraditionalForm\`s = 1\)]],
" return (0,\[Infinity]). Put interval data ",
Cell[BoxData[
\(TraditionalForm\`{1, 0, 0, 1, f, s}\)]],
" on ",
StyleBox["intervalstack",
FontSlant->"Italic"],
"."
}], "Text"],
Cell[TextData[{
"(2) If ",
StyleBox["intervalstack",
FontSlant->"Italic"],
" is empty, return ",
StyleBox["rootlist",
FontSlant->"Italic"],
", else take interval data ",
Cell[BoxData[
\(TraditionalForm\`{a, b, c, d, p, s}\)]],
" off ",
StyleBox["intervalstack",
FontSlant->"Italic"],
"."
}], "Text"],
Cell[TextData[{
"(3) Compute a lower bound ",
Cell[BoxData[
\(TraditionalForm\`\[Alpha]\)]],
" on positive roots of ",
Cell[BoxData[
\(TraditionalForm\`p\)]],
"."
}], "Text"],
Cell[TextData[{
"(4) If ",
Cell[BoxData[
\(TraditionalForm\`\[Alpha] > \[Alpha]\_0\)]],
" set ",
Cell[BoxData[
\(TraditionalForm\`\(p(x)\)\[LongLeftArrow]\(p(\[Alpha]\ x)\)\)]],
", ",
Cell[BoxData[
\(TraditionalForm\`a \[LeftArrow] \[Alpha]\ a\)]],
", ",
Cell[BoxData[
\(TraditionalForm\`c \[LeftArrow] \[Alpha]\ c\)]],
", ",
Cell[BoxData[
\(TraditionalForm\`\[Alpha] \[LeftArrow] 1\)]],
"."
}], "Text"],
Cell[TextData[{
"(5) If ",
Cell[BoxData[
\(TraditionalForm\`\[Alpha] \[GreaterEqual] 1\)]],
", set ",
Cell[BoxData[
\(TraditionalForm\`\(p(x)\)\[LongLeftArrow]\(p(x + \[Alpha])\)\)]],
", ",
Cell[BoxData[
\(TraditionalForm\`b \[LeftArrow] \[Alpha]\ a + b\)]],
",and ",
Cell[BoxData[
\(TraditionalForm\`c \[LeftArrow] \[Alpha]\ c\)]],
". If ",
Cell[BoxData[
\(TraditionalForm\`p(\ 0) = 0\)]],
", add ",
Cell[BoxData[
\(TraditionalForm\`\([b/d, b/d]\)\)]],
" to ",
StyleBox["rootlist",
FontSlant->"Italic"],
", and set ",
Cell[BoxData[
\(TraditionalForm\`\(p(x)\)\[LongLeftArrow]\(p(x)\)/x\)]],
". Compute ",
Cell[BoxData[
\(TraditionalForm\`s \[LeftArrow] sgc\ \((p)\)\)]],
". If ",
Cell[BoxData[
\(TraditionalForm\`s = 0\)]],
" go to step 2. If ",
Cell[BoxData[
\(TraditionalForm\`s = 1\)]],
", add ",
Cell[BoxData[
\(TraditionalForm\`intrv(a, b, c, d)\)]],
" to ",
StyleBox["rootlist",
FontSlant->"Italic"],
" and go to step 2."
}], "Text"],
Cell[TextData[{
"(6) Compute ",
Cell[BoxData[
\(TraditionalForm\`\(\(p\_1\)(x)\)\[LongLeftArrow]\(p(x + 1)\)\)]],
", and set ",
Cell[BoxData[
\(TraditionalForm\`a\_1 \[LeftArrow] a\)]],
", ",
Cell[BoxData[
\(TraditionalForm\`b\_1 \[LeftArrow] a + b\)]],
", ",
Cell[BoxData[
\(TraditionalForm\`c\_1 \[LeftArrow] c\)]],
", ",
Cell[BoxData[
\(TraditionalForm\`d\_1 \[LeftArrow] c + d\)]],
", and ",
Cell[BoxData[
\(TraditionalForm\`r \[LeftArrow] 0\)]],
". If ",
Cell[BoxData[
\(TraditionalForm\`\(p\_1\)(\ 0) = 0\)]],
", add ",
Cell[BoxData[
\(TraditionalForm\`\([b\_1\/d\_1, b\_1\/d\_1]\)\)]],
" to ",
StyleBox["rootlist",
FontSlant->"Italic"],
", and set ",
Cell[BoxData[
\(TraditionalForm\`\(\(p\_1\)(x)\)\[LongLeftArrow]\(\(p\_1\)(x)\)/
x\)]],
", and ",
Cell[BoxData[
\(TraditionalForm\`r \[LeftArrow] 1\)]],
". Compute ",
Cell[BoxData[
\(TraditionalForm\`s\_1 \[LeftArrow] sgc\ \((p\_1)\)\)]],
", and set ",
Cell[BoxData[
\(TraditionalForm\`s\_2 \[LeftArrow] s - s\_1 - r\)]],
", ",
Cell[BoxData[
\(TraditionalForm\`a\_2 \[LeftArrow] b\)]],
", ",
Cell[BoxData[
\(TraditionalForm\`b\_2 \[LeftArrow] a + b\)]],
", ",
Cell[BoxData[
\(TraditionalForm\`c\_2 \[LeftArrow] d\)]],
", ",
Cell[BoxData[
\(TraditionalForm\`d\_2 \[LeftArrow] c + d\)]],
". "
}], "Text"],
Cell[TextData[{
"(7) If ",
Cell[BoxData[
\(TraditionalForm\`s\_2 > 1\)]],
", compute ",
Cell[BoxData[
\(TraditionalForm\`\(\(p\_2\)(x)\)\[LongLeftArrow]\((x + 1)\)\^m \( p(
1\/\(x + 1\))\)\)]],
", where ",
Cell[BoxData[
\(TraditionalForm\`m\)]],
" is the degree of ",
Cell[BoxData[
\(TraditionalForm\`p\)]],
". If ",
Cell[BoxData[
\(TraditionalForm\`\(p\_2\)(\ 0) = 0\)]],
", set ",
Cell[BoxData[
\(TraditionalForm\`\(\(p\_2\)(x)\)\[LongLeftArrow]\(\(p\_2\)(x)\)/
x\)]],
". Compute ",
Cell[BoxData[
\(TraditionalForm\`s\_2 \[LeftArrow] sgc\ \((p\_2)\)\)]],
"."
}], "Text"],
Cell[TextData[{
"(8) If ",
Cell[BoxData[
\(TraditionalForm\`s\_1 < s\_2\)]],
", swap ",
Cell[BoxData[
\(TraditionalForm\`{a\_1, b\_1, c\_1, d\_1, p\_1, s\_1}\)]],
" with ",
Cell[BoxData[
\(TraditionalForm\`{a\_2, b\_2, c\_2, d\_2, p\_2, s\_2}\)]],
"."
}], "Text"],
Cell[TextData[{
"(9) If ",
Cell[BoxData[
\(TraditionalForm\`s\_1 = 0\)]],
" goto step 2. If ",
Cell[BoxData[
\(TraditionalForm\`s\_1 = 1\)]],
", add ",
Cell[BoxData[
\(TraditionalForm\`intrv(a\_1, b\_1, c\_1, d\_1)\)]],
" to ",
StyleBox["rootlist",
FontSlant->"Italic"],
", else put interval data ",
Cell[BoxData[
\(TraditionalForm\`{a\_1, b\_1, c\_1, d\_1, p\_1, s\_1}\)]],
" on ",
StyleBox["intervalstack",
FontSlant->"Italic"],
"."
}], "Text"],
Cell[TextData[{
"(10) If ",
Cell[BoxData[
\(TraditionalForm\`s\_2 = 0\)]],
" goto step 2. If ",
Cell[BoxData[
\(TraditionalForm\`s\_2 = 1\)]],
", add ",
Cell[BoxData[
\(TraditionalForm\`intrv(a\_2, b\_2, c\_2, d\_2)\)]],
" to ",
StyleBox["rootlist",
FontSlant->"Italic"],
", else put interval data ",
Cell[BoxData[
\(TraditionalForm\`{a\_2, b\_2, c\_2, d\_2, p\_2, s\_2}\)]],
" on ",
StyleBox["intervalstack",
FontSlant->"Italic"],
". ",
"Go to step 2."
}], "Text"],
Cell["\<\
Correctness of the above algorithm was proved and its computational \
complexity was discussed in [Akr1978b, Akr1980, Akr1989].\
\>", "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell["Memory usage", "Subsection"],
Cell["Conjecture", "Text"],
Cell[BoxData[
\(sgc \((p \((x + 1)\))\) +
sgc \((\(\((x + 1)\)\^n\) p \((1\/\(x + 1\))\))\) \[LessEqual]
sgc \((p \((x)\))\)\)], "DisplayFormula"],
Cell[TextData[{
"implies that the number of sign changes in any interval on ",
StyleBox["intervalstack",
FontSlant->"Italic"],
" is at least equal to the total number of sign changes in all intervals \
above it. Since the number of sign changes in the top interval is at least 2, \
and the total number of sign changes in all intervals on stack is at most the \
degree ",
Cell[BoxData[
\(TraditionalForm\`n\)]],
" of ",
Cell[BoxData[
\(TraditionalForm\`f\)]],
", the number of possible levels in\n",
StyleBox["intervalstack",
FontSlant->"Italic"],
" is at most ",
Cell[BoxData[
\(TraditionalForm\`\(log\_2\) n\)]],
". Therefore the maximal number of transformed polynomials we need to keep \
at any given time is at most ",
Cell[BoxData[
\(TraditionalForm\`1 + \(log\_2\) n\)]],
". "
}], "Text"]
}, Closed]]
}, Closed]],
Cell[CellGroupData[{
Cell["Experimental Results", "Section"],
Cell[TextData[{
"We compare performance of our continued fraction (CF) algorithm, and the \
algorithm REL described in [RZ2002]. We have implemented both algorithms as a \
part of ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" kernel. They both use the same implementation of Shaw and Traub's \
algorithm for Taylor shifts (see [GG1997]). As benchmark examples we use \
Chebyshev, Laguerre, Wilkinson, and Mignotte polynomials used in [RZ2002], as \
well as three types of randomly generated polynomials used in [ABS1994]."
}], "Text"],
Cell[TextData[{
"All computations were done on a 850 MHz Athlon PC with 256 MB RAM. The \
memory used data was obtained using ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" MaxMemoryUsed command, so it includes the total memory used by ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" kernel. The startup size of ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" kernel is 1.6 MB."
}], "Text"],
Cell["\<\
The results given for random polynomials were averaged over sets of \
5 random polynomials each, both methods were tested on the same sets of \
randomly generated polynomials. \
\>", "Text"],
Cell[CellGroupData[{
Cell["Special polynomials", "Subsection"],
Cell[TextData[{
"Here CF is faster by factors ranging from around 3 for Chebyshev \
polynomials to 50000 for Mignotte polynomials. The case of Mignotte \
polynomials is especially advantageous for our continued fractions method, \
because there is a point with a very simple continued fraction expansion \
(namely ",
Cell[BoxData[
\(TraditionalForm\`1\/5\)]],
"), which lies between the two close roots. For Chebyshev polynomials we \
used the fact that the polynomials are even and so with both methods we \
isolated only the positive roots."
}], "Text"],
Cell[BoxData[GridBox[{
{"Polynomial", "Degree", \(\(\ \ \)\(Number\ \ \[IndentingNewLine]
of\ Roots\)\), \(\(\ \ \ \ \ \ \ \ \ \)\(CF\[IndentingNewLine]
T \((s)\)/
M \((MB)\)\)\), \(\(\ \ \ \ \ \ \ \ \ \
\)\(REL\[IndentingNewLine]
T \((s)\)/M \((MB)\)\)\)},
{"Chebyshev", "1000", "1000", \(2172/9.2\), \(7368/8.5\)},
{"Chebyshev", "1200", "1200", \(4851/12.8\), \(15660/11.8\)},
{"Laguerre", "900", "900", \(3790/8.7\), \(22169/14.1\)},
{"Laguerre", "1000", "1000", \(6210/10.4\), \(34024/17.1\)},
{"Wilkinson", "800", "800", \(73.4/3.24\), \(3244/10\)},
{"Wilkinson", "900", "900", \(143/3.66\), \(5402/12.5\)},
{"Wilkinson", "1000", "1000", \(256/4.1\), \(8284/15.1\)},
{"Mignotte", "300", "4", \(0.12/1.75\), \(803/7.7\)},
{"Mignotte", "400", "4", \(0.22/1.77\), \(3422/15.8\)},
{"Mignotte", "600", "4", \(0.54/1.89\), \(26245/49.1\)}
}]], "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell["Polynomials with randomly generated coefficients", "Subsection"],
Cell["Here CF was faster by factors between 1.5 and 5.", "Text"],
Cell[BoxData[GridBox[{
{\(Coefficients\[IndentingNewLine]
\((bit\ length)\)\),
"Degree", \(\(\ \ \)\(Number\ \ \[IndentingNewLine]
of\ Roots\)\), \(\(\ \ \ \ \ \ \ \ \ \)\(CF\[IndentingNewLine]
T \((s)\)/
M \((MB)\)\)\), \(\(\ \ \ \ \ \ \ \ \ \
\)\(REL\[IndentingNewLine]
T \((s)\)/M \((MB)\)\)\)},
{"10", "500", "3.6", \(0.78/2.2\), \(1.66/2.81\)},
{"10", "1000", "4.4", \(6.67/3.75\), \(34.2/7.5\)},
{"10", "2000", "5.6", \(215/11.4\), \(562/22.8\)},
{"1000", "500", "3.2", \(0.56/2.28\), \(2.19/2.97\)},
{"1000", "1000", "3.6", \(12.7/5.1\), \(31.4/6.5\)},
{"1000", "2000", "6.0", \(329/14.2\), \(510/24.3\)}
}]], "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell["Monic polynomials with randomly generated coefficients", "Subsection"],
Cell["\<\
This case proved to be especially hard for REL. In this case CF was \
several thousand times faster. This is because such polynomials tend to have \
both very large and small roots, so an isolation method based on interval \
bisection starts with a very large interval, and needs to bisect it many \
times before it isolates the small roots. CF does not have this problem, \
because the size of its each ``step'' is based on an estimate of how far the \
next root is.\
\>", "Text"],
Cell[BoxData[GridBox[{
{\(Coefficients\[IndentingNewLine]
\((bit\ length)\)\),
"Degree", \(\(\ \ \)\(Number\ \ \[IndentingNewLine]
of\ Roots\)\), \(\(\ \ \ \ \ \ \ \ \ \)\(CF\[IndentingNewLine]
T \((s)\)/
M \((MB)\)\)\), \(\(\ \ \ \ \ \ \ \ \ \
\)\(REL\[IndentingNewLine]
T \((s)\)/M \((MB)\)\)\)},
{"10", "500", "5.2", \(1.43/2.48\), \(8.84/3.84\)},
{"10", "1000", "4.8", \(7.12/3.74\), \(80.7/10.1\)},
{"10", "2000", "6.8", \(263/11.4\), \(1001/37.1\)},
{"1000", "100", "4.4", \(0.01/1.75\), \(56.8/5.5\)},
{"1000", "200", "6.0", \(0.086/1.93\), \(252/17\)},
{"1000", "500", "5.6", \(0.57/2.28\), \(1917/96.8\)},
{"1000", "1000", "6.0", \(25.5/5.2\), \(\(>\)\(5000/?\)\)}
}]], "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell["Products of factors (x-randomly generated integer root)", "Subsection"],
Cell["\<\
Here CF was up to 25 times faster for small roots, but REL was up \
to 4 times faster for large roots. The latter being the only case when we \
found CF to be slower than REL.\
\>", "Text"],
Cell[BoxData[GridBox[{
{\(\(\ \ \ \ \ \ \ \)\(Roots\[IndentingNewLine]
\((bit\ length)\)\)\),
"Degree", \(\(\ \ \)\(Number\ \ \[IndentingNewLine]
of\ Roots\)\), \(\(\ \ \ \ \ \ \ \ \ \)\(CF\[IndentingNewLine]
T \((s)\)/
M \((MB)\)\)\), \(\(\ \ \ \ \ \ \ \ \ \
\)\(REL\[IndentingNewLine]
T \((s)\)/M \((MB)\)\)\)},
{"10", "100", "100", \(0.8/1.82\), \(0.61/1.92\)},
{"10", "200", "200", \(2.45/2.07\), \(10.1/2.64\)},
{"10", "500", "500", \(33.9/3.34\), \(878/8.4\)},
{"1000", "20", "20", \(0.12/1.88\), \(0.044/1.83\)},
{"1000", "50", "50", \(16.7/3.18\), \(4.27/2.86\)},
{"1000", "100", "100", \(550/8.9\), \(133/6.49\)}
}]], "Text"]
}, Closed]]
}, Closed]],
Cell[CellGroupData[{
Cell["Conclusions", "Section"],
Cell["\<\
We have shown that our continued fraction root isolation algorithm \
is almost always faster than the algorithms based on interval bisection. Its \
bound on memory usage, given in terms of the number of transformed \
polynomials it needs to keep, is not much worse then for the algorithm REL \
presented in [RZ2002], and in practice its memory usage is often smaller than \
that of REL.\
\>", "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell["References", "Section"],
Cell[TextData[{
"[Akr1978] Alkiviadis G. Akritas, ",
StyleBox["A correction on a theorem by Uspensky",
FontSlant->"Italic"],
", Bulletin of the Greek Mathematical Society, 19 (1978), pp. 278-285.\n\
[Akr1978b] Alkiviadis G. Akritas, ",
StyleBox["Vincent's theorem in algebraic manipulation",
FontSlant->"Italic"],
", Ph.D. thesis, North Carolina State University, Raleigh, N.C., 1978.\n\
[Akr1980] Alkiviadis G. Akritas, ",
StyleBox["An implementation of Vincent's Theorem",
FontSlant->"Italic"],
", Numerische Mathematik, \\textbf{36}(1980), pp. 53-62.\n[Akr1982] \
Alkiviadis G. Akritas, ",
StyleBox["Reflections on a pair of theorems by Budan and Fourier",
FontSlant->"Italic"],
", Mathematics Magazine, 55 (1982), pp. 292-298.\n[Akr1984] Alkiviadis G. \
Akritas, Budan's theorem and its consequences, Sciences et Techniques en \
Perspective, 4 (1984), pp. 1-13.\n[Akr1989] Alkiviadis G. Akritas, Elements \
of Computer Algebra-with Applications, Wiley, New York, NY, 1989. Available \
also in Russian, MIR Publishers, Moscow, 1994 (with new material).\n[ABS1994] \
Alkiviadis G. Akritas, Alexei V. Bocharov and Adam W. Strzebonski, ",
StyleBox["Implementation of real root isolation algorithms in Mathematica",
FontSlant->"Italic"],
", Abstracts of the International Conference on Interval and \
Computer-Algebraic Methods in Science and Engineering (Interval'94), \
St.Petersburg, Russia, March 7-10, (1994), pp.23-27.\n[AD1980] Alkiviadis G. \
Akritas and Stylianos D. Danielopoulos, ",
StyleBox["On the complexity of algorithms for the translation of \
polynomials",
FontSlant->"Italic"],
", Computing, 24 (1980), pp. 51-60.\n[CA1976] George E. Collins and \
Alkiviadis G. Akritas, ",
StyleBox["Polynomial real root isolation using Descartes' rule of signs",
FontSlant->"Italic"],
", Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic \
Computations, Yorktown Heights, N.Y., (1976), pp. 272-275.\n[GG1997] Joachim \
von zur Gathen and Jurgen Gerhard, ",
StyleBox["Fast Algorithms for Taylor Shifts and Certain Difference \
Equations",
FontSlant->"Italic"],
", Proceedings of ISSAC'97, Maui, Hawaii, U.S.A., (1997), pp. 40-47.\n\
[LT1972] S. Lang and H. Trotter, ",
StyleBox["Continued fractions for some algebraic numbers",
FontSlant->"Italic"],
", Journal fur die reine und angewandte Mathematik, 255 (1972), pp. \
122-134.\n[RZ2002] Fabrice Rouillier and Paul Zimmermann, ",
StyleBox["Efficient isolation of polynomial real roots",
FontSlant->"Italic"],
", preprint, 2002.\n[U1948] J. V. Uspensky, ",
StyleBox["Theory of Equations",
FontSlant->"Italic"],
", McGraw-Hill, New York, 1948.\n[V1836] A. J. H. Vincent, ",
StyleBox["Sur la resolution des equations numeriques",
FontSlant->"Italic"],
", Journal de Mathematiques Pures et Appliquees, 1 (1836), pp. 341-372."
}], "Text"]
}, Closed]]
}, Open ]]
}, Open ]]
},
FrontEndVersion->"4.1 for X",
ScreenRectangle->{{0, 1024}, {0, 768}},
WindowSize->{798, 608},
WindowMargins->{{Automatic, 83}, {Automatic, 50}},
Magnification->1.25,
StyleDefinitions -> "ArticleClassic.nb"
]
(*******************************************************************
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->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[CellGroupData[{
Cell[1727, 52, 72, 0, 157, "Title"],
Cell[1802, 54, 39, 0, 48, "Author"],
Cell[1844, 56, 129, 3, 22, "Address"],
Cell[CellGroupData[{
Cell[1998, 63, 37, 0, 48, "Author"],
Cell[2038, 65, 101, 3, 22, "Address"],
Cell[2142, 70, 2038, 40, 357, "Abstract"],
Cell[CellGroupData[{
Cell[4205, 114, 61, 0, 66, "Section"],
Cell[4269, 116, 105, 3, 31, "Text"],
Cell[4377, 121, 540, 16, 69, "Text"],
Cell[4920, 139, 163, 3, 56, "DisplayFormula"],
Cell[5086, 144, 288, 11, 31, "Text"],
Cell[5377, 157, 103, 2, 60, "DisplayFormula"],
Cell[5483, 161, 270, 8, 31, "Text"],
Cell[5756, 171, 142, 3, 85, "DisplayFormula"],
Cell[5901, 176, 248, 8, 31, "Text"],
Cell[6152, 186, 657, 19, 69, "Text"],
Cell[6812, 207, 295, 5, 69, "Text"],
Cell[7110, 214, 213, 4, 50, "Text"],
Cell[7326, 220, 467, 9, 88, "Text"],
Cell[7796, 231, 270, 5, 69, "Text"],
Cell[8069, 238, 762, 28, 50, "Text"],
Cell[8834, 268, 280, 8, 50, "Text"],
Cell[9117, 278, 605, 18, 69, "Text"],
Cell[9725, 298, 614, 18, 69, "Text"],
Cell[10342, 318, 269, 5, 69, "Text"],
Cell[10614, 325, 624, 18, 73, "Text"],
Cell[11241, 345, 765, 20, 92, "Text"],
Cell[12009, 367, 400, 9, 88, "Text"],
Cell[12412, 378, 137, 3, 31, "Text"],
Cell[12552, 383, 344, 11, 50, "Text"],
Cell[12899, 396, 288, 9, 50, "Text"],
Cell[13190, 407, 174, 4, 50, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[13401, 416, 49, 0, 33, "Section"],
Cell[13453, 418, 187, 4, 50, "Text"],
Cell[13643, 424, 985, 28, 107, "Text"],
Cell[14631, 454, 602, 16, 69, "Text"],
Cell[15236, 472, 71, 0, 31, "Text"],
Cell[15310, 474, 720, 24, 61, "Text"],
Cell[16033, 500, 375, 11, 50, "Text"],
Cell[16411, 513, 446, 7, 88, "Text"],
Cell[16860, 522, 730, 15, 126, "Text"],
Cell[17593, 539, 581, 13, 89, "Text"],
Cell[18177, 554, 417, 15, 50, "Text"],
Cell[18597, 571, 69, 1, 31, "Text"],
Cell[18669, 574, 166, 3, 54, "DisplayFormula"],
Cell[CellGroupData[{
Cell[18860, 581, 50, 0, 51, "Subsection"],
Cell[18913, 583, 504, 15, 50, "Text"],
Cell[19420, 600, 152, 3, 35, "DisplayFormula"],
Cell[19575, 605, 21, 0, 31, "Text"],
Cell[19599, 607, 234, 4, 53, "DisplayFormula"],
Cell[19836, 613, 651, 26, 50, "Text"],
Cell[20490, 641, 268, 9, 31, "Text"],
Cell[20761, 652, 430, 16, 69, "Text"],
Cell[21194, 670, 529, 20, 50, "Text"],
Cell[21726, 692, 336, 14, 31, "Text"],
Cell[22065, 708, 196, 8, 31, "Text"],
Cell[22264, 718, 457, 17, 31, "Text"],
Cell[22724, 737, 1069, 41, 69, "Text"],
Cell[23796, 780, 1442, 54, 76, "Text"],
Cell[25241, 836, 662, 25, 54, "Text"],
Cell[25906, 863, 295, 11, 31, "Text"],
Cell[26204, 876, 504, 20, 50, "Text"],
Cell[26711, 898, 525, 21, 50, "Text"],
Cell[27239, 921, 151, 3, 50, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[27427, 929, 34, 0, 30, "Subsection"],
Cell[27464, 931, 26, 0, 31, "Text"],
Cell[27493, 933, 166, 3, 54, "DisplayFormula"],
Cell[27662, 938, 853, 24, 109, "Text"]
}, Closed]]
}, Closed]],
Cell[CellGroupData[{
Cell[28564, 968, 39, 0, 33, "Section"],
Cell[28606, 970, 549, 10, 107, "Text"],
Cell[29158, 982, 426, 12, 69, "Text"],
Cell[29587, 996, 200, 4, 50, "Text"],
Cell[CellGroupData[{
Cell[29812, 1004, 41, 0, 51, "Subsection"],
Cell[29856, 1006, 567, 11, 110, "Text"],
Cell[30426, 1019, 1001, 18, 280, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[31464, 1042, 70, 0, 30, "Subsection"],
Cell[31537, 1044, 64, 0, 31, "Text"],
Cell[31604, 1046, 764, 16, 188, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[32405, 1067, 76, 0, 30, "Subsection"],
Cell[32484, 1069, 491, 8, 88, "Text"],
Cell[32978, 1079, 834, 17, 212, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[33849, 1101, 77, 0, 30, "Subsection"],
Cell[33929, 1103, 199, 4, 50, "Text"],
Cell[34131, 1109, 774, 16, 188, "Text"]
}, Closed]]
}, Closed]],
Cell[CellGroupData[{
Cell[34954, 1131, 30, 0, 33, "Section"],
Cell[34987, 1133, 410, 7, 88, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[35434, 1145, 29, 0, 33, "Section"],
Cell[35466, 1147, 2899, 56, 544, "Text"]
}, Closed]]
}, Open ]]
}, Open ]]
}
]
*)
(*******************************************************************
End of Mathematica Notebook file.
*******************************************************************)