(*********************************************************************** Mathematica-Compatible Notebook This notebook can be used on any computer system with Mathematica 3.0, MathReader 3.0, or any compatible application. The data for the notebook starts with the line of 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[ 39665, 1001]*) (*NotebookOutlinePosition[ 76538, 1987]*) (* CellTagsIndexPosition[ 76494, 1983]*) (*WindowFrame->Normal*) Notebook[{ Cell[TextData[{ StyleBox["Mathematica", FontSlant->"Italic"], " Numerics for developers" }], "Subtitle"], Cell[TextData[StyleBox["Cholesky decomposition", "Subsubtitle"]], "Subtitle"], Cell[CellGroupData[{ Cell["Stored Timings and Plots", "Subsection"], Cell[BoxData[ \(Needs["\"]\)], "Input"], Cell[BoxData[ \(Ctimes\ = \ Table[\n\tn\ = \ Round[2^j]; \n\tA\ = \ makepdsmatrix[n, True]; \n\t t\ = \ time[cd\ = \(CholeskyDecomposition[A]\)[\([1]\)]]; \n\t err\ = \ Max[Abs[A\ - \ cd . Transpose[cd]]]; \n\t{n, t, err}, \n \t{j, 1, 9, .5}]\)], "Input", Evaluatable->False], Cell[BoxData[ \(\(Ctimes\ = \ {{2, 0.00009704589843749999`, 8.881784197001252`*^-16}, {3, 0.00009887695312500006`, 1.7763568394002505`*^-15}, {4, 0.00010253906249999998`, 3.552713678800501`*^-15}, {6, 0.00011047363281250014`, 7.105427357601002`*^-15}, {8, 0.00013305664062499955`, 1.4210854715202004`*^-14}, {11, 0.0001660156250000008`, 2.842170943040401`*^-14}, {16, 0.00026611328125000083`, 5.684341886080802`*^-14}, {23, 0.0005029296875000006`, 2.2737367544323206`*^-13}, {32, 0.0010644531249999964`, 1.1368683772161603`*^-12}, {45, 0.002519531250000012`, 9.094947017729282`*^-13}, {64, 0.0064453124999999944`, 3.637978807091713`*^-12}, {91, 0.01781250000000001`, 1.4551915228366852`*^-11}, {128, 0.04874999999999985`, 3.2741809263825417`*^-11}, {181, 0.13125000000000053`, 4.729372449219227`*^-11}, {256, 0.3775000000000013`, 1.8917489796876907`*^-10}, {362, 1.0250000000000057`, 1.7462298274040222`*^-10}, {512, 3.0799999999999983`, 1.1059455573558807`*^-9}}; \)\)], "Input"], Cell[BoxData[ \(\(Cp\ = \ LogLogListPlot[\(#[\([{1, 2}]\)]&\)\ /@\ Ctimes, PlotJoined -> True, DisplayFunction -> Identity]; \)\)], "Input"], Cell[BoxData[ \(\(times1\ = \ {{2, 0.00164062500000000666`, 0.`}, {3, 0.00318359374999999111`, 1.77635683940025046`*^-15}, {4, 0.00499999999999989341`, 3.55271367880050092`*^-15}, {6, 0.0109374999999998223`, 7.10542735760100185`*^-15}, {8, 0.0246875000000006394`, 1.42108547152020037`*^-14}, {11, 0.0390625`, 2.84217094304040074`*^-14}, {16, 0.0962499999999977262`, 5.68434188608080148`*^-14}, {23, 0.252499999999997726`, 1.13686837721616029`*^-13}, {32, 0.550000000000011368`, 2.27373675443232059`*^-13}, {45, 1.17999999999994997`, 4.54747350886464118`*^-13}, {64, 3.03999999999996362`, 1.81898940354585647`*^-12}, {91, 7.76999999999998181`, 1.81898940354585647`*^-12}, {128, 20.3100000000000591`, 7.2759576141834259`*^-12}, {181, 54.4400000000000527`, 1.09139364212751388`*^-11}, {256, 148.339999999999916`, 2.91038304567337036`*^-11}, {362, 419.850000000000012`, 4.36557456851005554`*^-11}, {512, 1166.99999999999981`, 1.16415321826934814`*^-10}}; \)\)], "Input"], Cell[BoxData[ \(\(p1\ = \ LogLogListPlot[\(#[\([{1, 2}]\)]&\)\ /@\ times1, PlotStyle -> {RGBColor[0, 0, 0], PointSize[0.025]}, DisplayFunction -> Identity]; \)\)], "Input"], Cell[BoxData[ \(\(times2\ = \ {{2, 0.00139648437499999978`, 0.`}, {3, 0.00242187499999999689`, 1.77635683940025046`*^-15}, {4, 0.00351562500000000133`, 3.55271367880050092`*^-15}, {6, 0.006249999999999992`, 7.10542735760100185`*^-15}, {8, 0.00882812500000001953`, 1.42108547152020037`*^-14}, {11, 0.0139843749999999932`, 2.84217094304040074`*^-14}, {16, 0.0254687499999999822`, 5.68434188608080148`*^-14}, {23, 0.0478124999999999289`, 2.27373675443232059`*^-13}, {32, 0.0912499999999998223`, 2.27373675443232059`*^-13}, {45, 0.188749999999999751`, 4.54747350886464118`*^-13}, {64, 0.447499999999999786`, 1.81898940354585647`*^-12}, {91, 1.10999999999999943`, 3.63797880709171295`*^-12}, {128, 2.89000000000000056`, 7.2759576141834259`*^-12}, {181, 8.46999999999999886`, 1.09139364212751388`*^-11}, {256, 23.270000000000004`, 2.91038304567337036`*^-11}, {362, 66.6600000000000125`, 4.36557456851005554`*^-11}, {512, 181.980000000000003`, 1.16415321826934814`*^-10}}; \)\)], "Input"], Cell[BoxData[ \(\(p2\ = \ LogLogListPlot[\(#[\([{1, 2}]\)]&\)\ /@\ times2, PlotStyle -> {RGBColor[0, 1, 0], PointSize[0.025]}, DisplayFunction -> Identity]; \)\)], "Input"], Cell[BoxData[ \(\(times3\ = \ {{2, 0.000280761718749911182`, 8.88178419700125232`*^-16}, {3, 0.000466308593750186517`, 1.77635683940025046`*^-15}, {4, 0.000742187499999769073`, 3.55271367880050092`*^-15}, {6, 0.00158203124999989341`, 7.10542735760100185`*^-15}, {8, 0.00300781249999992894`, 1.42108547152020037`*^-14}, {11, 0.00652343750000028421`, 2.84217094304040074`*^-14}, {16, 0.01953125`, 5.68434188608080148`*^-14}, {23, 0.0662500000000250111`, 1.13686837721616029`*^-13}, {32, 0.221249999999940882`, 2.27373675443232059`*^-13}, {45, 0.800000000000181898`, 4.54747350886464118`*^-13}, {64, 2.96999999999934516`, 9.09494701772928237`*^-13}, {91, 16.4200000000000727`, 1.81898940354585647`*^-12}, {128, 90.7499999999999928`, 3.63797880709171295`*^-12}}; \)\)], "Input"], Cell[BoxData[ \(\(p3\ = \ LogLogListPlot[\(#[\([{1, 2}]\)]&\)\ /@\ times3, PlotStyle -> {RGBColor[0, 0, 1], PointSize[0.025]}, DisplayFunction -> Identity]; \)\)], "Input"], Cell[BoxData[ \(\(ptimes1\ = \ {{2, 0.0013183593750001332`, 8.881784197001252`*^-16}, {3, 0.002675781250000231`, 1.7763568394002505`*^-15}, {4, 0.004570312500000284`, 0.`}, {6, 0.010390625000001208`, 7.105427357601002`*^-15}, {8, 0.018906249999997016`, 1.4210854715202004`*^-14}, {11, 0.03812500000000085`, 2.842170943040401`*^-14}, {16, 0.08937500000000398`, 5.684341886080802`*^-14}, {23, 0.21250000000000568`, 1.1368683772161603`*^-13}, {32, 0.4824999999999591`, 2.2737367544323206`*^-13}, {45, 1.1600000000000819`, 4.547473508864641`*^-13}, {64, 2.9700000000000273`, 9.094947017729282`*^-13}, {91, 8.029999999999973`, 1.8189894035458565`*^-12}, {128, 21.04000000000019`, 3.637978807091713`*^-12}, {181, 56.649999999999864`, 7.275957614183426`*^-12}, {256, 154.84000000000015`, 1.4551915228366852`*^-11}, {362, 428.8299999999999`, 2.9103830456733704`*^-11}, {512, 1197.62`, 5.820766091346741`*^-11}}; \)\)], "Input"], Cell[BoxData[ \(\(pp1\ = \ LogLogListPlot[\(#[\([{1, 2}]\)]&\)\ /@\ ptimes1, PlotStyle -> {RGBColor[ .25, .25, .25], PointSize[0.025]}, DisplayFunction -> Identity]; \)\)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(ptimes2\ = \ {{2, 0.0013574218749998757`, 8.881784197001252`*^-16}, {3, 0.0022460937499997335`, 1.7763568394002505`*^-15}, {4, 0.0031249999999998224`, 3.552713678800501`*^-15}, {6, 0.0049218749999999645`, 7.105427357601002`*^-15}, {8, 0.006757812500000071`, 1.4210854715202004`*^-14}, {11, 0.009609375000000142`, 1.4210854715202004`*^-14}, {16, 0.014531250000000995`, 5.684341886080802`*^-14}, {23, 0.022187500000001137`, 1.1368683772161603`*^-13}, {32, 0.03531250000000341`, 2.2737367544323206`*^-13}, {45, 0.05187499999999545`, 4.547473508864641`*^-13}, {64, 0.08249999999999602`, 9.094947017729282`*^-13}, {91, 0.14124999999998522`, 1.8189894035458565`*^-12}, {128, 0.27000000000003865`, 3.637978807091713`*^-12}, {181, 0.5750000000000455`, 7.275957614183426`*^-12}, {256, 1.3900000000001`, 1.4551915228366852`*^-11}, {362, 3.709999999999809`, 2.9103830456733704`*^-11}, {512, 9.720000000000027`, 5.820766091346741`*^-11}}\)], "Input"], Cell[BoxData[ \({{2, 0.0013574218749998757`, 8.881784197001252`*^-16}, {3, 0.0022460937499997335`, 1.7763568394002505`*^-15}, {4, 0.0031249999999998224`, 3.552713678800501`*^-15}, {6, 0.0049218749999999645`, 7.105427357601002`*^-15}, {8, 0.006757812500000071`, 1.4210854715202004`*^-14}, {11, 0.009609375000000142`, 1.4210854715202004`*^-14}, {16, 0.014531250000000995`, 5.684341886080802`*^-14}, {23, 0.022187500000001137`, 1.1368683772161603`*^-13}, {32, 0.03531250000000341`, 2.2737367544323206`*^-13}, {45, 0.05187499999999545`, 4.547473508864641`*^-13}, {64, 0.08249999999999602`, 9.094947017729282`*^-13}, {91, 0.14124999999998522`, 1.8189894035458565`*^-12}, {128, 0.27000000000003865`, 3.637978807091713`*^-12}, {181, 0.5750000000000455`, 7.275957614183426`*^-12}, {256, 1.3900000000001`, 1.4551915228366852`*^-11}, {362, 3.709999999999809`, 2.9103830456733704`*^-11}, {512, 9.720000000000027`, 5.820766091346741`*^-11}}\)], "Output"] }, Open ]], Cell[BoxData[ \(\(pp2\ = \ LogLogListPlot[\(#[\([{1, 2}]\)]&\)\ /@\ ptimes2, PlotStyle -> {RGBColor[0, .5, .5], PointSize[0.025]}, DisplayFunction -> Identity]; \)\)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(ptimes3\ = \ {{2, 0.00013427734375001665`, 8.881784197001252`*^-16}, {3, 0.0002075195312499778`, 1.7763568394002505`*^-15}, {4, 0.0003027343750000022`, 3.552713678800501`*^-15}, {6, 0.00056640625000004`, 2.220446049250313`*^-16}, {8, 0.0009228515625000488`, 1.4210854715202004`*^-14}, {11, 0.001708984375`, 1.4210854715202004`*^-14}, {16, 0.0036328125000002487`, 5.684341886080802`*^-14}, {23, 0.007343750000000426`, 1.1368683772161603`*^-13}, {32, 0.015234375000000355`, 2.2737367544323206`*^-13}, {45, 0.03187499999999943`, 4.547473508864641`*^-13}, {64, 0.06937499999999375`, 9.094947017729282`*^-13}, {91, 0.16499999999999204`, 1.8189894035458565`*^-12}, {128, 0.37000000000000455`, 3.637978807091713`*^-12}, {181, 0.8699999999998909`, 7.275957614183426`*^-12}, {256, 2.4299999999998363`, 1.4551915228366852`*^-11}, {362, 6.230000000000018`, 2.9103830456733704`*^-11}, {512, 16.710000000000036`, 5.820766091346741`*^-11}}\)], "Input"], Cell[BoxData[ \({{2, 0.00013427734375001665`, 8.881784197001252`*^-16}, {3, 0.0002075195312499778`, 1.7763568394002505`*^-15}, {4, 0.0003027343750000022`, 3.552713678800501`*^-15}, {6, 0.00056640625000004`, 2.220446049250313`*^-16}, {8, 0.0009228515625000488`, 1.4210854715202004`*^-14}, {11, 0.001708984375`, 1.4210854715202004`*^-14}, {16, 0.0036328125000002487`, 5.684341886080802`*^-14}, {23, 0.007343750000000426`, 1.1368683772161603`*^-13}, {32, 0.015234375000000355`, 2.2737367544323206`*^-13}, {45, 0.03187499999999943`, 4.547473508864641`*^-13}, {64, 0.06937499999999375`, 9.094947017729282`*^-13}, {91, 0.16499999999999204`, 1.8189894035458565`*^-12}, {128, 0.37000000000000455`, 3.637978807091713`*^-12}, {181, 0.8699999999998909`, 7.275957614183426`*^-12}, {256, 2.4299999999998363`, 1.4551915228366852`*^-11}, {362, 6.230000000000018`, 2.9103830456733704`*^-11}, {512, 16.710000000000036`, 5.820766091346741`*^-11}}\)], "Output"] }, Open ]], Cell[BoxData[ \(\(pp3\ = \ LogLogListPlot[\(#[\([{1, 2}]\)]&\)\ /@\ ptimes3, PlotStyle -> {RGBColor[ .5, 0, 1], PointSize[0.025]}, DisplayFunction -> Identity]; \)\)], "Input"], Cell[BoxData[ \(\(ptimes4\ = \ {{2, 0.0007666015624999967`, 8.881784197001252`*^-16}, {3, 0.0013281249999999994`, 1.7763568394002505`*^-15}, {4, 0.0018457031250000144`, 3.552713678800501`*^-15}, {6, 0.002832031249999978`, 7.105427357601002`*^-15}, {8, 0.004140625000000009`, 1.4210854715202004`*^-14}, {11, 0.007656250000000031`, 1.4210854715202004`*^-14}, {16, 0.014140625000000018`, 5.684341886080802`*^-14}, {23, 0.020624999999999893`, 1.1368683772161603`*^-13}, {32, 0.024218750000000178`, 2.2737367544323206`*^-13}, {45, 0.04062499999999947`, 4.547473508864641`*^-13}, {64, 0.08000000000000007`, 9.094947017729282`*^-13}, {91, 0.19875000000000043`, 1.8189894035458565`*^-12}, {128, 0.6550000000000011`, 3.637978807091713`*^-12}, {181, 1.7700000000000102`, 7.275957614183426`*^-12}, {256, 4.949999999999989`, 1.4551915228366852`*^-11}, {362, 13.060000000000002`, 2.9103830456733704`*^-11}, {512, 36.79999999999998`, 5.820766091346741`*^-11}}; \)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Deriving the decomposition", "Subsection"], Cell["\<\ For a thorough explanation see \"Matrix Computations\", Gene Golub \ and Charles Van Loan, 3rd ed, Johns Hopkins, 1996\ \>", "Text"], Cell[BoxData[ \(\((A\ = \ Table[If[i\ >= \ j, a\_\(i, j\), a\_\(j, i\)], {i, 1, 4}, {j, 1, 4}])\)\ // \ MatrixForm\)], "Input"], Cell[BoxData[ \(\((L\ = \ \ Table[If[i\ >= \ j, l\_\(i, j\), 0], {i, 1, 4}, {j, 1, 4}])\)\ // \ MatrixForm\)], "Input"], Cell[BoxData[ \(\((prod\ = \ L . Transpose[L])\)\ // \ MatrixForm\)], "Input"], Cell[BoxData[ \(rules\ = \ {l\_\(1, 1\) -> \@a\_\(1, 1\)}; \n prod\ /. \ rules\ // MatrixForm\)], "Input"], Cell[BoxData[ \(rules\ = \ Join[rules, {l\_\(j_, 1\ \) \[RuleDelayed] a\_\(j, 1\)\/l\_\(1, 1\)}]; \nprod\ //. rules\ // \ MatrixForm\)], "Input"], Cell[BoxData[ \(rules\ = \ Join[rules, { l\_\(2, 2\ \) -> \@\(a\_\(2, 2\) - a\_\(2, 1\)\^2\/a\_\(1, 1\)\)}]; \nprod\ //. rules\ // \ MatrixForm\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Implementation 1", "Subsection"], Cell[TextData[ "To make coding more convenient, define a function that determines if the \ diagonal element is large enough to use. A tolerance \[Epsilon] is used to \ avoid dividing by numbers that are too small."], "Text"], Cell[BoxData[ \(setdiagonal[j_, \[Epsilon]_]\ := \ \n\t If[\[Epsilon]\ === \ Symbolic\ || \ L[\([j, j]\)]\ > \ \[Epsilon], \n \t\tL[\([j, j]\)]\ = \ \@L[\([j, j]\)], \n\ \ \ \ (*\ else\ *) \n \t\tMessage[CholeskyDecomposition::posdef]; \n\t\tThrow[$Failed], \n \t\t (*\ inequality\ didn' t\ eval\ *) \n\t\t Message[CholeskyDecomposition::neval, \ L[\([j, j]\)], \[Epsilon]]; \n \t\tThrow[$Failed]]\)], "Input"], Cell["I'll explain the reason for this definition later", "Text"], Cell[BoxData[ \(\(zero\ = \ 0; \)\)], "Input"], Cell[TextData[ "Here is a function that, given the matrix and a tolerance \[Epsilon], will \ compute the Cholesky decomposition. It makes a copy of the matrix and then \ does the computation in place in the matrix L. "], "Text"], Cell[BoxData[ \(CholeskyDecomposition1[a_, \[Epsilon]_]\ := \ \n\t Block[{n\ = \ Length[a], L\ = \ a}, \n\t\tsetdiagonal[1, \[Epsilon]]; \n\t\tDo[\n\t\t\tDo[L[\([j - 1, i]\)]\ = \ zero, {i, j, n}]; \n\t\t\t Do[L[\([i, j - 1]\)]\ /= \ L[\([j - 1, j\ - 1]\)], {i, j, n}]; \n \t\t\tDo[ L[\([i, j]\)]\ -= \ Sum[L[\([i, k]\)]*L[\([j, k]\)], {k, 1, j - 1}], {i, j, n}]; \n \t\t\tsetdiagonal[j, \[Epsilon]], \n\t\t\t{j, 2, n}]; \n\t\tL]\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Verification", "Subsection"], Cell["For exact input 0 tolerance is reasonable.", "Text"], Cell[BoxData[ \(CholeskyDecomposition1[{{2, 1}, {1, 1}}, 0]\)], "Input"], Cell[BoxData[ \(% . Transpose[%]\)], "Input"], Cell[TextData[{ "Because we have written this in ", StyleBox["Mathematica", FontSlant->"Italic"], ", the function is polymorphic for many types: in particular, exact \ numeric data (as shown above), symbolic matrices, machine number matrices, \ and arbitrary precision matrices. Some more examples" }], "Text"], Cell[BoxData[ \(\((A\ = \ Table[If[i\ >= \ j, a\_\(i, j\), a\_\(j, i\)], {i, 1, 3}, {j, 1, 3}])\)\ // \ MatrixForm\)], "Input"], Cell[TextData[ "In this case, the data is symbolic, and we will not be able to verify the \ positivity of the diagonal elements before taking the square root, so we give \ \[Epsilon] === Symbolic which causes setdiagonal to ignore this."], "Text"], Cell[BoxData[ \(CholeskyDecomposition1[A, Symbolic]\)], "Input"], Cell[BoxData[ \(Simplify[% . Transpose[%]]\ // \ MatrixForm\)], "Input"], Cell["Here is a random symmetric matrix", "Text"], Cell[BoxData[ \(A\ = \ Table[Random[Integer, {\(-9\), 9}], {4}, {4}]; \n A\ += \ Transpose[A]; \nMatrixForm[A]\)], "Input"], Cell["\<\ One (relatively fast) way to determine if the matrix is positive \ definite is to simply try to Cholesky decomposition. \ \>", "Text"], Cell[BoxData[ \(CholeskyDecomposition1[A, 0]\)], "Input"], Cell["\<\ This matrix will be diagonally dominant and thus positive \ definite\ \>", "Text"], Cell[BoxData[ \(A\ += \ 100\ IdentityMatrix[4]\ // \ MatrixForm\)], "Input"], Cell["With an exact matrix, the decompostion will be exact", "Text"], Cell[BoxData[ \(cd\ = \ CholeskyDecomposition1[A, 0]; \n Simplify[A\ - \ cd . Transpose[cd]]\)], "Input"], Cell[TextData[ "The problem with using exact quantities is that the computations will become \ increasingly complex for bigger matrices. These problems can be reduced by \ using an L.D.Transpose[L] decomposition instead, but the complexity still \ becomes overwhelming for large matrices. For most applications, numerical \ data is quite sufficient. For example, with machine numbers, it is \ appropriate to use machine \[Epsilon], and "], "Text"], Cell[BoxData[ \(cd\ = \ CholeskyDecomposition1[N[A], $MachineEpsilon]; \n A\ - \ cd . Transpose[cd]\)], "Input"], Cell[TextData[ "With arbitrary precision numbers, the tolerance should be associated with \ the precision of the numbers. In analogy with machine \[Epsilon], define"], "Text"], Cell[BoxData[ \(N\[Epsilon][prec_]\ := \ N[2^\((1 - Floor[prec*Log[2, 10]])\)]\)], "Input"], Cell[BoxData[ \(N\[Epsilon][$MachinePrecision]\ === \ $MachineEpsilon\)], "Input"], Cell["\<\ Now we obtain the accuracy you would expect from higher precision \ input.\ \>", "Text"], Cell[BoxData[ \(cd\ = \ CholeskyDecomposition1[N[A, 32], N\[Epsilon][32]]; \n A\ - \ cd . Transpose[cd]\)], "Input"], Cell["\<\ So, with a relatively simple definition, we now have a function \ that computes a Cholesky decomposition for generic type. The next question \ is how fast does it run?\ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Asymptotic timing", "Subsection"], Cell[TextData[{ "Theoretically, the complexity of the decomposition is ", Cell[BoxData[ \(TraditionalForm \`\(O(n\^3)\) . \ \ Lets\ do\ some\ timings\ and\ \ \(see . \)\)]] }], "Text"], Cell[BoxData[ \(makepdsmatrix[n_]\ := \ Module[{A}, \n\t\tA\ = \ Table[Random[], {n}, {n}]; \n\t\t A\ += \ Transpose[A]; \n\t\tA\ += \ n^2\ IdentityMatrix[n]; \n\t\tA] \)], "Input"], Cell["\<\ This makes sure we don't run into the granularity of the operating \ system's timing facilities\ \>", "Text"], Cell[BoxData[ \(SetAttributes[time, \ HoldAll]; \n time[expr_]\ := \ Block[{Second\ = \ 1, t, \ tries\ = \ 1}, \ \n\ \ \ \ t\ = \ \(Timing[expr; ]\)[\([1]\)]; \ \ \ \ \n\ \ \ \ While[t\ < \ 1. , tries\ *= \ 2; t\ = \ \(Timing[Do[expr, {tries}]; ]\)[\([1]\)]]; \n\ \ \ \ t/tries]; \)], "Input"], Cell["\<\ If you want to check asymptotic complexity, often a good way to do \ it is to try the function over a large range of magnitudes. Here we use a \ loop which increases the system size exponentially. This has the advantage \ that on a log-log plot, the data will be equally spaced. \ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(times1\ = \ Table[\n\tn\ = \ Round[2^j]; \n\tA\ = \ makepdsmatrix[n]; \n\t t\ = \ time[cd\ = CholeskyDecomposition1[A, $MachineEpsilon]]; \n\t err\ = \ Max[Abs[A\ - \ cd . Transpose[cd]]]; \n\t{n, t, err}, \n \t{j, 1, 9, .5}]\)], "Input"], Cell[BoxData[ \({{2, 0.00164062500000000666`, 0.`}, {3, 0.00318359374999999111`, 1.77635683940025046`*^-15}, {4, 0.00499999999999989341`, 3.55271367880050092`*^-15}, {6, 0.0109374999999998223`, 7.10542735760100185`*^-15}, {8, 0.0246875000000006394`, 1.42108547152020037`*^-14}, {11, 0.0390625`, 2.84217094304040074`*^-14}, {16, 0.0962499999999977262`, 5.68434188608080148`*^-14}, {23, 0.252499999999997726`, 1.13686837721616029`*^-13}, {32, 0.550000000000011368`, 2.27373675443232059`*^-13}, {45, 1.17999999999994997`, 4.54747350886464118`*^-13}, {64, 3.03999999999996362`, 1.81898940354585647`*^-12}, {91, 7.76999999999998181`, 1.81898940354585647`*^-12}, {128, 20.3100000000000591`, 7.2759576141834259`*^-12}, {181, 54.4400000000000527`, 1.09139364212751388`*^-11}, {256, 148.339999999999916`, 2.91038304567337036`*^-11}, {362, 419.850000000000012`, 4.36557456851005554`*^-11}, {512, 1166.99999999999981`, 1.16415321826934814`*^-10}}\)], "Output"] }, Open ]], Cell["\<\ These timings were done a a Pentium PRO 200, which is a tad faster \ than this machine -- for comparison,\ \>", "Text"], Cell[BoxData[ \(timeshere\ = \ Table[\n\tn\ = \ Round[2^j]; \n\tA\ = \ makepdsmatrix[n]; \n\t t\ = \ time[cd\ = CholeskyDecomposition1[A, $MachineEpsilon]]; \n\t err\ = \ Max[Abs[A\ - \ cd . Transpose[cd]]]; \n\t{n, t, err}, \n \t{j, 1, 3, .5}]\)], "Input"], Cell[BoxData[ \(Needs["\"]\)], "Input"], Cell[BoxData[ \(\(p1\ = \ LogLogListPlot[\(#[\([{1, 2}]\)]&\)\ /@\ times1, PlotStyle -> PointSize[0.025]]; \)\)], "Input"], Cell[BoxData[ \(Clear[n]; \n Fit[Log[Take[\(#[\([{1, 2}]\)]&\)\ /@\ times1, \(-4\)]], {1, \[Xi]}, \[Xi]]\)], "Input"], Cell["\<\ The problem is that this is getting quite slow as n gets large. \ Just for comparison, we compare timings with an implementation of the \ Cholesky decomposition written in C.\ \>", "Text"], Cell[BoxData[ \(\(Show[p1, Cp, DisplayFunction -> $DisplayFunction, PlotRange -> All]; \)\)], "Input"], Cell[BoxData[ \(Clear[n]; \n Fit[Log[\(#[\([{1, 2}]\)]&\)\ /@\ Take[Ctimes, \(-8\)]], {1, \[Xi]}, \[Xi]]\)], "Input"], Cell[TextData[{ "The asymptotic complexity is the same ", Cell[BoxData[ \(TraditionalForm\`O(n\^3)\)]], " The difference in coefficient, however is huge:" }], "Text"], Cell[BoxData[ \(times1[\([\(-1\), 2]\)]/Ctimes[\([\(-1\), 2]\)]\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Implementation 2", "Subsection"], Cell[TextData[{ "Before we blame ", StyleBox["Mathematica", FontSlant->"Italic"], " as being \"too slow\", lets work on the program a bit." }], "Text"], Cell[TextData[{ "Asymptotically, the majority of the time is going to be spent on the \ innermost loop, which occurs in the ", StyleBox["Sum", "Input"], " command. An examination of this indicates that this command is really \ just implementing a dot product. In fact, if we look to the next loop out, \ we can see that it is really implementing a (sub)matrix-vector product. But \ since ", StyleBox["Mathematica", FontSlant->"Italic"], " has a command to do this which is optimized for machine numbers, it seems \ sensible to use it." }], "Text"], Cell[BoxData[ \(CholeskyDecomposition2[a_, \ \[Epsilon]_]\ := \n\t Block[{L, \ \ n\ = \ Length[a], rc, rr}, \n\t\tL\ = \ a; \ \n\t\t setdiagonal[1, \[Epsilon]]; \n\ \ \ \ Do[\n\t\t\trc\ = \ Range[j, \ n]; \ \n\t\t\t rr\ = \ Range[1, j - 1]; \n\t\t\t L[\([rc, j - 1]\)]\ /= \ L[\([j - 1, j - 1]\)]; \n\t\t\t L[\([rc, j]\)]\ -= \ L[\([rc, rr]\)] . L[\([j, rr]\)]; \n\t\t\t setdiagonal[j, \[Epsilon]]; \ \n\t\t\tL[\([rr, j]\)]\ = \ zero, \ \n\t\t\t{j, \ 2, \ n}]; \n\t\t\ L]\)], "Input"], Cell["We do a similar set of timing for this routine...", "Text"], Cell[BoxData[ \(\(times2\ = \ Table[\n\tn\ = \ Round[2^j]; \n\tA\ = \ makepdsmatrix[n]; \n\t t\ = \ time[cd\ = CholeskyDecomposition2[A, $MachineEpsilon]]; \n\t err\ = \ Max[Abs[A\ - \ cd . Transpose[cd]]]; \n\t{n, t, err}, \n \t{j, 1, 9, .5}]; \)\)], "Input"], Cell["The plot shows that we have made a significant improvement.", "Text"], Cell[BoxData[ \(\(Show[p1, p2, Cp, DisplayFunction -> $DisplayFunction, PlotRange -> All]; \)\)], "Input"], Cell["Just to be sure, we can check the complexity", "Text"], Cell[BoxData[ \(Clear[n]; \n fit2\ = \ Fit[Log[Take[\(#[\([{1, 2}]\)]&\)\ /@\ times2, \(-4\)]], {1, \[Xi]}, \[Xi]]\)], "Input"], Cell["It looks better, but we are still not even close!", "Text"], Cell[BoxData[ \({times1[\([\(-1\), 2]\)]/times2[\([\(-1\), 2]\)], times2[\([\(-1\), 2]\)]/Ctimes[\([\(-1\), 2]\)]}\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["The Compiler", "Subsection"], Cell[TextData[{ "The next option we have is to use the ", StyleBox["Mathematica", FontSlant->"Italic"], " compiler. Because ", StyleBox["Compile", "Input"], " is a ", StyleBox["HoldAll", "Input"], " function, we need to change out definition somewhat -- we have included \ the ", StyleBox["setdiagonal", "Input"], " functionality inline, and have modified the ", Cell[BoxData[ FormBox[ StyleBox["If", "Input"], TraditionalForm]]], " in that to return consistent type." }], "Text"], Cell[BoxData[ \(CholeskyDecomposition3\ = \ Compile[{{a, \ _Real, \ 2}, {\[Epsilon], \ _Real}}, \n\t\t Block[{L\ = \ a, \ \ n\ = \ Length[a], rc\ = \ Range[1], rr\ = \ Range[1], d}, \n\t\t\t If[L[\([1, 1]\)] > \ \[Epsilon], \n\t\t\t\t \(d\ = \ \(L[\([1, 1]\)]\ = \ Sqrt[L[\([1, 1]\)]]\); \), \(Return[{{0. }}]; \)]; \n\t\t\t Do[\t\n\t\t\t\trr\ = \ Range[1, j - 1]; \t\n\t\t\t\t Do[\t\n\t\t\t\t\tL[\([i, j - 1]\)]\ /= \ d; \ \ \n\t\t\t\t\t L[\([i, j]\)]\ -= \ L[\([i, rr]\)] . L[\([j, rr]\)], \n \t\t\t\t\t{i, j, n}]; \n\t\t\t\t If[L[\([j, j]\)] > \ \[Epsilon], \ \(d\ = \ \(L[\([j, j]\)]\ = \ Sqrt[L[\([j, j]\)]]\); \), \(Return[{{0. }}]; \)]; \n\t\t\t\t Do[L[\([i, j]\)]\ = \ 0. , \ {i, 1, j - 1}], \n \t\t\t\t{j, \ 2, \ n}]; \n\t\t\tL]]\)], "Input"], Cell["A similar timing ...", "Text"], Cell[BoxData[ \(\(times3\ = \ Table[\n\tn\ = \ Round[2^j]; \n\tA\ = \ makepdsmatrix[n]; \n\t t\ = \ time[cd\ = CholeskyDecomposition3[A, $MachineEpsilon]]; \n\t err\ = \ Max[Abs[A\ - \ cd . Transpose[cd]]]; \n\t{n, t, err}, \n \t{j, 1, 7, .5}]; \)\)], "Input"], Cell["... shows that something is amiss!!", "Text"], Cell[BoxData[ \(\(Show[p1, p2, p3, Cp, DisplayFunction -> $DisplayFunction, PlotRange -> All]; \)\)], "Input"], Cell["A computation of the asymptotic complexity shows ...", "Text"], Cell[BoxData[ \(Clear[n]; \n fit3\ = \ Fit[Log[Take[\(#[\([{1, 2}]\)]&\)\ /@\ times3, \(-4\)]], {1, \[Xi]}, \[Xi]]\)], "Input"], Cell["... that something is way wrong. The reason why is subtle.", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["PackedArray objects.", "Subsection"], Cell[TextData[{ "A ", StyleBox["PackedArray", "Input"], " object is a special internal implementation of a list essentially the \ same as what the ", StyleBox["Mathematica", FontSlant->"Italic"], " compiler uses. Unless you really want to know, a PackedArray feels, \ smells, and tastes just like a list. To the internals of ", StyleBox["Mathematica", FontSlant->"Italic"], ", however, they are quite different. Just like in the ", StyleBox["Mathematica", FontSlant->"Italic"], " compiler, they must be rectangular tensors, and all of the same type \ amongst machine integers, real, or complex numbers. " }], "Text"], Cell["\<\ Since the matrices we have been trying timings for satisfy this \ definition, this is a good candidate problem for PackedArrays. \ \>", "Text"], Cell["First redefine the matrix generator we use", "Text"], Cell[BoxData[ \(makepdsmatrix[n_, packed_: False]\ := \ Module[{A}, \n\t\tA\ = \ Table[Random[], {n}, {n}]; \n\t\t A\ += \ Transpose[A]; \n\t\tA\ += \ n^2\ IdentityMatrix[n]; \n\t\t If[packed, Developer`Pack[A], Developer`Unpack[A]]]\)], "Input"], Cell["\<\ There is a function to check if a list is stored internally as a \ PackedArray or not:\ \>", "Text"], Cell[BoxData[ \(Developer`PackedArrayQ[makepdsmatrix[3, False]]\)], "Input"], Cell[BoxData[ \(Developer`PackedArrayQ[A\ = \ makepdsmatrix[3, True]]\)], "Input"], Cell["It still looks just like a list", "Text"], Cell[BoxData[ \(A\)], "Input"], Cell["and we can give it to our command", "Text"], Cell[BoxData[ \(setdiagonal[j_, \[Epsilon]_]\ := \ \n\t If[\[Epsilon]\ === \ Symbolic\ || \ L[\([j, j]\)]\ > \ \[Epsilon], \n \t\tL[\([j, j]\)]\ = \ Sqrt[L[\([j, j]\)]], \n \ \ \ \ (*\ else\ *) \n\t\tMessage[CholeskyDecomposition::posdef]; \n \t\tThrow[$Failed], \n\t\t (*\ inequality\ didn' t\ eval\ *) \n\t\t Message[CholeskyDecomposition::neval, \ L[\([j, j]\)], \[Epsilon]]; \n \t\tThrow[$Failed]]\)], "Input", CellOpen->False], Cell[BoxData[ \(\(zero\ = \ 0; \)\)], "Input", CellOpen->False], Cell[BoxData[ \(CholeskyDecomposition1[a_, \[Epsilon]_]\ := \ \n\t Block[{n\ = \ Length[a], L\ = \ a}, \n\t\tsetdiagonal[1, \[Epsilon]]; \n\t\tDo[\n\t\t\tDo[L[\([j - 1, i]\)]\ = \ zero, {i, j, n}]; \n\t\t\t Do[L[\([i, j - 1]\)]\ /= \ L[\([j - 1, j\ - 1]\)], {i, j, n}]; \n \t\t\tDo[ L[\([i, j]\)]\ -= \ Sum[L[\([i, k]\)]*L[\([j, k]\)], {k, 1, j - 1}], {i, j, n}]; \n \t\t\tsetdiagonal[j, \[Epsilon]], \n\t\t\t{j, 2, n}]; \n\t\tL]\)], "Input", CellOpen->False], Cell[BoxData[ \(CholeskyDecomposition1[A, $MachineEpsilon]\)], "Input"], Cell[BoxData[ \(Developer`PackedArrayQ[%]\)], "Input"], Cell["To get this to work, we need to redefine", "Text"], Cell[BoxData[ \(\(zero\ = \ 0. ; \)\)], "Input"], Cell["So the whole matrix consists of floating point numbers", "Text"], Cell[BoxData[ \(CholeskyDecomposition1[A, $MachineEpsilon]\)], "Input"], Cell[BoxData[ \(Developer`PackedArrayQ[%]\)], "Input"], Cell["So what does this do to the timings?", "Text"], Cell[BoxData[ \(\(ptimes1\ = \ Table[\n\tn\ = \ Round[2^j]; \n\tA\ = \ makepdsmatrix[n, True]; \n\t t\ = \ time[cd\ = CholeskyDecomposition1[A, $MachineEpsilon]]; \n\t err\ = \ Max[Abs[A\ - \ cd . Transpose[cd]]]; \n\t{n, t, err}, \n \t{j, 1, 9, .5}]; \)\)], "Input", CellLabel->"In[18]:="], Cell[BoxData[ \(CholeskyDecomposition2[a_, \ \[Epsilon]_]\ := \n\t Block[{L, \ \ n\ = \ Length[a], rc, rr}, \n\t\tL\ = \ a; \ \n\t\t setdiagonal[1, \[Epsilon]]; \n\ \ \ \ Do[\n\t\t\trc\ = \ Range[j, \ n]; \ \n\t\t\t rr\ = \ Range[1, j - 1]; \n\t\t\t L[\([rc, j - 1]\)]\ /= \ L[\([j - 1, j - 1]\)]; \n\t\t\t L[\([rc, j]\)]\ -= \ L[\([rc, rr]\)] . L[\([j, rr]\)]; \n\t\t\t setdiagonal[j, \[Epsilon]]; \ \n\t\t\tL[\([rr, j]\)]\ = \ zero, \ \n\t\t\t{j, \ 2, \ n}]; \n\t\t\ L]\)], "Input", CellLabel->"In[37]:=", CellOpen->False], Cell[BoxData[ \(\(ptimes2\ = \ Table[\n\tn\ = \ Round[2^j]; \n\tA\ = \ makepdsmatrix[n, True]; \n\t t\ = \ time[cd\ = CholeskyDecomposition2[A, $MachineEpsilon]]; \n\t err\ = \ Max[Abs[A\ - \ cd . Transpose[cd]]]; \n\t{n, t, err}, \n \t{j, 1, 9, .5}]; \)\)], "Input", CellLabel->"In[19]:="], Cell[BoxData[ \(\(CholeskyDecomposition3\ = \ Compile[{{a, \ _Real, \ 2}, {\[Epsilon], \ _Real}}, \n\t\t Block[{L\ = \ a, \ \ n\ = \ Length[a], rc\ = \ Range[1], rr\ = \ Range[1], d}, \n\t\t\t If[L[\([1, 1]\)] > \ \[Epsilon], \n\t\t\t\t \(d\ = \ \(L[\([1, 1]\)]\ = \ Sqrt[L[\([1, 1]\)]]\);\), \(Return[{{0. }}]; \)]; \n\t\t\t Do[\t\n\t\t\t\trr\ = \ Range[1, j - 1]; \t\n\t\t\t\t Do[\t\n\t\t\t\t\tL[\([i, j - 1]\)]\ /= \ d; \ \ \n\t\t\t\t\t L[\([i, j]\)]\ -= \ L[\([i, rr]\)] . L[\([j, rr]\)], \n \t\t\t\t\t{i, j, n}]; \n\t\t\t\t If[L[\([j, j]\)] > \ \[Epsilon], \ \(d\ = \ \(L[\([j, j]\)]\ = \ Sqrt[L[\([j, j]\)]]\); \), \(Return[{{0. }}]; \)]; \n\t\t\t\t Do[L[\([i, j]\)]\ = \ 0. , \ {i, 1, j - 1}], \n \t\t\t\t{j, \ 2, \ n}]; \n\t\t\tL]]; \)\)], "Input", CellLabel->"In[21]:=", CellOpen->False], Cell[BoxData[ \(\(ptimes3\ = \ Table[\n\tn\ = \ Round[2^j]; \n\tA\ = \ makepdsmatrix[n, True]; \n\t t\ = \ time[cd\ = CholeskyDecomposition3[A, $MachineEpsilon]]; \n\t err\ = \ Max[Abs[A\ - \ cd . Transpose[cd]]]; \n\t{n, t, err}, \n \t{j, 1, 9, .5}]; \)\)], "Input", CellLabel->"In[22]:="], Cell[BoxData[ \(\(Show[p1, p2, p3, pp1, pp2, pp3, Cp, DisplayFunction -> $DisplayFunction, PlotRange -> All]; \)\)], "Input"], Cell["\<\ The second version with packed arrays is almost as fast as compiled \ C code.\ \>", "Text"], Cell[BoxData[ \({times2[\([\(-1\), 2]\)]/ptimes2[\([\(-1\), 2]\)], ptimes2[\([\(-1\), 2]\)]/Ctimes[\([\(-1\), 2]\)]}\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Improving the user interface", "Subsection"], Cell[TextData[ "There is really no reason that a user should have to worry about the value \ of the tolerance variable \[Epsilon] used to ensure there are no division \ problems. Also, as you can see there are big advantages to having the matrix \ be represented as a PackedArray. It is also a good idea to check that the \ matrix is symmetric, too."], "Text"], Cell[BoxData[ \(\(CholeskyDecomposition::symm\ = \ "\"; \)\)], "Input"], Cell[BoxData[ \(\(CholeskyDecomposition::neval\ = \ "\"; \)\)], "Input"], Cell[BoxData[ \(\(CholeskyDecomposition::posdef\ = \ "\"; \)\)], "Input"], Cell[BoxData[ \(\(MyCholeskyDecomposition[a_]\ := \ With[{cd\ = \ Catch[MyCholesky[a]]}, cd\ /; \ cd\ =!= \ $Failed]; \)\)], "Input"], Cell[BoxData[ \(MyCholesky[a_]\ := \ Module[{A\ = \ a, dims, \ prec, \ machine, \ symbolic, \ \[Epsilon]}, \n\t\tdims\ = \ Dimensions[A]; \n\t\t If[Length[dims]\ < \ 2\ || \ Not[MatrixQ[A]], \n\t\t\t Message[CholeskyDecomposition::matrix, A, 1]; \n\t\t Throw[$Failed]]; \n\t\t If[dims[\([1]\)]\ != \ dims[\([2]\)], \ \n\t\t\t\t Message[CholeskyDecomposition::matsq, A, 1]; \tThrow[$Failed]]; \n \t\tIf[\(! SameQ[A, Transpose[A]]\), \ \n\t\t\t\t Message[CholeskyDecomposition::symm, A, 1]; \tThrow[$Failed]]; \n \t\tprec\ = \ Infinity; \n\t\tmachine\ = \ False; \n\t\t symbolic\ = \ False; \n\t\t ftest\ \ = \ Function[{x}, If[MachineNumberQ[x], machine\ = \ True; \ True, \n\t\t\t\t If[Not[NumericQ[x]], \ symbolic\ = \ True; \ False, \n \t\t\t\t\t\t If[x\ != \ 0, prec\ = \ Min[Precision[x], prec], prec\ = \ Min[Accuracy[x], prec]]; \ True]]]; \n\t\t MatrixQ[A, ftest]; \n\t\t If[machine, \n\t\t\tA\ = \ N[A]; \n\t\t\t \[Epsilon]\ = \ If[MatrixQ[A, NumberQ], $MachineEpsilon, Symbolic], \n \t\t\t (*\ else\ *) \n\t\t\t If[symbolic, \n\t\t\t\t\[Epsilon]\ = \ Symbolic, \n \t\t\t\t (*\ else\ *) \n\t\t\t\tA\ = \ N[A, prec]; \[Epsilon]\ = \ 2^\((1\ - \ Floor[Log[2. , 10]*prec])\)]]; \n \t\tBlock[{zero}, If[machine, zero\ = \ 0. , \ zero\ = \ 0]; CholeskyDecomposition2[A, \[Epsilon]]]]\)], "Input"], Cell[BoxData[ \(MyCholeskyDecomposition[{{1, 2}, {3, 4}}]\)], "Input"], Cell[BoxData[ \(MyCholeskyDecomposition[{{1. , 1}, {1, 1}}]\)], "Input"], Cell[BoxData[ \(MyCholeskyDecomposition[{{2, 1}, {1, 1}}]\)], "Input"], Cell[BoxData[ \(MyCholeskyDecomposition[{{2. , 1}, {1, 1}}]\)], "Input"], Cell[BoxData[ \(MyCholeskyDecomposition[{{2`20, 1}, {1, 1}}]\)], "Input"], Cell["\<\ So with this definition, concerns about precision and \ numeric/symbolic data are handled automatically.\ \>", "Text"] }, Closed]] }, FrontEndVersion->"X 3.0", ScreenRectangle->{{0, 800}, {0, 600}}, ScreenStyleEnvironment->"Presentation", Evaluator->"Local", WindowSize->{754, 481}, WindowMargins->{{Automatic, 4}, {0, Automatic}}, StyleDefinitions -> Notebook[{ Cell[CellGroupData[{ Cell["Style Definitions", "Subtitle"], Cell["\<\ Modify the definitions below to change the default appearance of \ all cells in a given style. Make modifications to any definition using \ commands in the Format menu.\ \>", "Text"], Cell[CellGroupData[{ Cell["Style Environment Names", "Section"], Cell[StyleData[All, "Working"], PageWidth->WindowWidth, ScriptMinSize->9], Cell[StyleData[All, "Printout"], PageWidth->PaperWidth, ScriptMinSize->7, FontSize->10, PrivateFontOptions->{"FontType"->"Outline"}] }, Closed]], Cell[CellGroupData[{ Cell["Notebook Options", "Section"], Cell["\<\ The options defined for the style below will be used at the \ Notebook level.\ \>", "Text"], Cell[StyleData["Notebook"], PageHeaders->{{Cell[ TextData[ { CounterBox[ "Page"]}], "PageNumber"], None, Cell[ TextData[ { ValueBox[ "FileName"]}], "Header"]}, {Cell[ TextData[ { ValueBox[ "FileName"]}], "Header"], None, Cell[ TextData[ { CounterBox[ "Page"]}], "PageNumber"]}}, PageHeaderLines->{True, True}, PrintingOptions->{"FirstPageHeader"->False, "FacingPages"->True}, CellBracketOptions->{"Color"->RGBColor[0, 0, 0.466667]}, StyleMenuListing->None] }, Closed]], Cell[CellGroupData[{ Cell["Header Graphic (to be pasted in)", "Section"], Cell[CellGroupData[{ Cell[StyleData["HeaderCell"], ShowCellBracket->False, CellMargins->{{0, 0}, {0, 0}}, Evaluatable->False, PageBreakBelow->False, ImageSize->{350, 24}, ImageMargins->{{0, 0}, {0, 0}}, ImageRegion->{{0, 1}, {0, 1}}, StyleMenuListing->None], Cell[GraphicsData["Bitmap", "\<\ CF5dJ6E]HGAYHf4PAg9QL6QYHgLNmh4Ool00gOoJg]c_@05Ool01GOoJke[NfnLOmh0g7oo001YOol047?oDeU6DTV]CHa1cSIc?YAJ mgNmOomSW56<@NlfLe[g0Woo00U_oe=U8nU5lGMmh0fWoo001XOol00f_NH:El0005O000 16R4=Li2eVIB0g`000EXHcHaKke__FAS00El0004H:D^4DjDMmkIOol006Moo`03Nomh07`000Ql0003 >Q1l07`000=l0003CLeO_G`000Ql0003Nkmo_W^oNmik_gnoNmio_g_OOmmkgWnoOmmkg`Aog`03NmmoggoO009og`03OomoggoO065oo`00 001000SP@00Hd4CP@=10h43PA=102>1001C@@>10h43P@=1000SP@0014h43@@>10d43P@=14h43@@>10d43P@=1000SP@00Ld43P@=14h43@@>10d4@02>10013@@>10d 43P@0S@@001000SP@00Td43P@>10d43PA>10d43P@=1000cP@00Ld43P@=10h43@@>10d4002 >1001C@@>10h43P@=1000SP@00@d43P@>10d408h4006=10h43@@>10d4CP?1G`000O00017`0 00I41W`0O01l05`W?2h5O0000f`2O01l0003O0001B@692dlDT1a?7800T2B00A0Td2bA;=4/`94d`03 A?A8m4Sd00995003CAE9=DdD009=E@03DEIAME5e009AMP05DIIEUUFFEIME]P02EKL015WGEMMIeeGG 15Wh00aN65XHGQQN65hhGQQN>F8hHUUR>69IGUT3HUT0369iHWYVNF9jIWUVNV:IIYYVNVJJI[YZVP9V ^P06J[]Z^V[KJ[]ZffkK0f[K00=Znf[lK_/00Vkk0VlL00=_6flLK_`00WA=A4ddBcA=A0e5B_O05d0g@SN05TB3Cg:?QP 9@Al0006:6X`eEB?B;8`nW0S17`000BAA=5Ddd009==@03DEE=EU5E00=A MP9EUP0=DIIEUeFgEKII]eGGFMMEeeggFOMIf5hHFOP00ehH00MN>5hIGSQN>68iHUUN>@03HUT01f9i IUURNFIjHWYVVFIj00AVVP09IY]V^VZJI[]Z^VZkI[]ZfVZj00EZf`07K_]ZnfkLJ_]^nfklK_/00Vkl 00I_6flLKaa^o7?LlecSF?=I8/dAY00El0005 ;;50e42d@=@he`04O00017006914dcCi17`000Id01b^A?===DTECC@2CCD01E5ECEEAEE5fDGD00U5f 0UFF00aE]UFgEKII]eGGFKQEeeWhFOMIn5ggFOP4GQP2GST2HSP6HUT01fIjHUUVNF9jIWURVVIi009V VP05JYYVVfJjJYYV^`02J[X00fZkJ]]Z^P03J]/02fkKJ]]^nf[KK_]Zo6kkJaa^o6kkK_`00VlL00Uc 6flLLaa_?7CaBGQQVVUWGIWYEUUVgIWYIf0=RF@0>IYYE]ddeIYYRFEWG@794m5Vg?59= EFJJGQUN60=RF@0:HSTlLTBcIYYIn68iGQQ=EFZjFOP2HST06D2C@99I]fJjFMQRNEgh?98h46JJMii^ fflLB?AAUVIjIYYAMT1bEGIVVUWGIYYEUT2B00=4/`03A=@leFA800El0006>6/le4RdA==0]3cE17`0 00EH0b2>A;@lmg0T00Al00046:e954dECA@3CCD07deEDEEAEU5eDEIAUUFFDIIEUeFfEIME]eGGFKME eeWgFMMImeghFOQJ65hGGOQN65hiGQQR>5iIHSUNF68i00=RF@08HWYVFF9iHWYRNFIjIYUVNP=VVP03 I[YVVVJk009Z^P05I[]Z^fJjJ]]Z^`05J]/01FkkJ]a^nfkkK_`00Vkk00=_76kkKa`00flL00Ec76lL Laac?6lL009c?00=Leec?7=LLcecG7114ddde009oo`07A;=^ o7oOA==4/d2BBCD00Woo00=8m4BcDIH00Woo00U954BB@9=8lehIOomgGDCC>1000Woo00i8e42BHUUo oe5FOomRFDCC@9=4dehIOomkWT2c0dBc00A4ddBc?=I/A`Al0007>4LEhHGST2HST00eiIHSURF@02HUT0269jIWURNVIiHWYVVVJI IWX4IYX01fZjIY]V^VZjJ[]ZffZj009Zf`0EJ[]ZffkKJ_]ZffkkJ_a^g6kkK_a_76kkKaa^o7150/caAHSUooeFF?790DT2BOomEUS@@DEERNS`aA;35AMG15_73`a?79EUWooIWTh11gOCPA@;=4/c@?OomZVSPA@;3@@FMMoocPa@790/SPAGQQ^fd2b IYXl=Ml07`000=l 000316/PSR2a00Al0006K00TdDdEBAA==Ddd0Tde00Y=EE5FCEEAEU5eDGIEUU6FEIME]P=E]`9Ie`06 EMMIeeWgGOQIn5Wg0ehH015N>EhHGSQR>EiHHSURFEiIHUURNF9IIWURFVIiHWYVNVIi00EVVP09J[YV VfZjJ[YZ^fJkJ[YZ^fJk009Zf`035k_SaB?34`46ZkOolh4D2c@;90TWooFMLlLP02A;<013PaNgioocPA0TBc038h 4GooIYXlDDBc>11oofIj?554/dSd?790TSaALce0TcaAHUYoogMn@78h154 /gooEKI0LTBc?35c?Goo>114ddBcA=68iHSUNF68i169I00ERNVIiHWUVNF:J009VNP03IYUVVVJK009VVP05J[YV^fZj I[YZ^`03J]/016ZjJ]]ZffkK0V[K00I^nfklK_]ZnfklKa/2K_`00flKKaac7002Ka`01W114ddBc>15oof9J?554ddBc?55Z^goo<0llLT1b =0moogMM>354/cPAOom^o30??55gGCaAA;=0LVIjEIHd47^NOom8m6kk=11R>Goo>354TSaBOom_775hH HSUN>5hiHST01F9I00QVNV9iIWYRNVIiIWYRVFIj0fJJ00UV^VZkIYYZ^fZjJ]YZ^fZjJ[/00V[K00a^ ff[KJ_]^nf[KK_aZnfklKa]^o6kkLa`4Ka`01g11oog^o>354/cPa Okm0LSQAOomZfc`a0094/`0:=11oogMM>354/dCC?59In7ooGOP2HUT0K_aoocP@A;=4d`02A;<0342cA;=M/A`Ul000>D4Lm5DceBAA=54TECCA==DeECCEAEDeEDGIAM@9AMP9EUP05DIMI ]eFfFMME]`02FML015WgFOQImeWh0UhH00UMmehHGQQN>EhHHUUR>5hiGUT00f9I00MRNF9IIUYRNFIj HWYVN@04IYX01fJjJYYV^VZkI[YV^fZj009Zf`05J[YZff[KJ]]^f`02J]/04FkkJ_]^o6kkJ_]^o6lL K_]_77;lKaac76llLaa_77E6F>11ooeWG?594ddBc?35g OWoo>1000TBc02M0LU5EOomIeddeDII8m6klOolh44Bc?55Z^gooA==N67oo?550/dBc@79^o3P@OomR FC`aDIIRFD2COom9541cA;94/fkl;0ioog^n>1400TBc00E0LTdeOom==D2B0094/`0:?79Mn7oo=11A MWooA;=0TTBcA=<2A;<024CC@79R>E6F>11ooeWG?782A;<00ccFE8il0007O0001E1Y>=I4]4BcA=<0 0dBc00@03HUQR>F9I00=RF@07IWYRNVIiHWYV NFJJIWX00VJJ00YZVVJJIYYVVfJjJ[]Z^VJkJ[YV^`9Zf`031ooc@?KaaoocPAA;=0/dBbK_a=5GooB?A0TT2CA;5hiHUUN>@06HUT01fIi HWYVNF9jIYUVNVJI009VVP0:IY]Z^VJkJYYV^VZkJ[YZffZjJ[/4J]/016kkJ]]^nf[k0Vkl00A^nfkl Kaa^n`E_7004Lcac77GooB?A0TT1bHUUIn5ghOollD@94/`0T?59IegooOolh44SdDCDlLCabGQQoocaA@;=0LTde >35oof9J?554/d2BDEEoodTD@98lTUEfOom9541c@990LTSDA==0TdCC0Woo02Q0TT2C@99EUVIjOomI md1AA;=0TTBcMgeooeFg?35EUcaA@;?LleD2dA;=0d`03A;<00dCCA;=0/`02 A;<023cD?=HheccF??LleTCeA=<3B?@014dDBAE==DdD0Tde01E=EE5ECEEAMU5EDGIAUUFFDIME]UFG EKMIeUFgFMMEeeWhFMMIn5hHFOL00ehH00AN>5hHGSUN>09R>@03GUQRFF9I009RF@06IWYRNV9IHWYV VFIj16JJ00YV^VJJJYYV^VZkJ[YV^fZkJ]]Z^P=Zf`05K]]Zff[KJ]]^o002K_/00f[lKa]^n`02Ka`0 17;lKaac?6lL0W10lLWooB=@d 44BcOom4/cPAA==ogbP=OomgGC0@A;34017oo@;=4TR`>0Woo 00Pl11oog^NCEEooe5f@994/dCC0dBc00E0ddBcA;=4/dCC00=4/`0< A==4/dBcA;=4ddBcA==4/dCCA;=0/dBd0TCC00i8e4SdA?=8m4TDCAA954TeCCEA=DeEDEEAEU5e0U5f 00EEMU6FEIIE]eFf009E]`03FMMEeeWG009Im`9In003GOQJ65hH009N6006GSUN668iGSQRFF8i0V9I 00URNF9IIUURNFIjHWUVNV:IIWX016JJ00MV^VJKJ[YV^VZkJ[YZ^`06J]/00fkkJ]]^n`02J_/01Fkl K_]^o6lLK_/00VlL00ec76lLLca_76llLca_?7114/dCC?79E]goOOom953ab0TBc00llDFZkNihh DCaBHUUoofIjK_]oog^NHWUoog^nGQP00Woo00A^o4CCCAEgO@9oo`03HYU95GMM009oo`07J[YZ^goo Oolh44SdK_`00Woo00Dh4DBcA;=0TTTD009oo`0EhH HSUN>F9IGSQN>@02HUT01VIIHUURNFIjHWYRN@9VNP03IYUVNVZJ00=VVP0?J[YVVfZjI[YZ^f[KI[YZ ^f[KJ[]ZnfkKJ]]^nf[K009^o007J_]^nfklKa]^o6lLKa/00VlL00Ec76llLaa_?GMgegOW^MMgigWG^NMiikWG^NMkikWW^nNkmo _P9k_P07Nkmk_W_ONkiogg_NNml00goO00=oogoOOol0EGoo00002TBcA==4/dBc@;90TehhOomkWSPa 0dBc00Dd47ooOomc7D2B0094/`0V@;=0/TdD@9=4/d2BDGI8ldCD>354ddSdBAAA=E5f@;=0TUWG@;=8 m5FF?558deFGB==EUSaaA;=E]eEfCEE4TT2CA==E]dCCA;=0/P=4/`04@794ddSdEKL2A;<05dCC@798 m4BbA;=0TU5EBAA8m3ab?59=54BcDGI4/eFg@794/eVgA;=0/c`aA;800UhH00Y4/cPaA;=4dd2c@998 m3aAB?A0LP=4/`05A==4/dBcA;=4d`03A;<01DCCA;=4/dBcA=<00dBc00=4ddBcA;<014Bc00A4ddCD B=A8l`98m003BAA95DdD00===@03CEEAEU5E009AMP0=EGIAMU6FEIIE]eFFFKME]UVgEMQIeeWgFML0 0UWh00=J65ghGQP00UhH00AN>EhhHSQR>@9RF@0;GUURFF9IHUUVFV9iIWUVNV9iIWYRVP03IYX026Jj JYYV^fZjI[]Z^VZkJ[X2J]/02FZkJ]]Zff[KK_]ZffkkJ_]^n`02K_`01VlLK_a_6fklKaac709_700; Laac?75hhHSURF5iI169I00MRNVIjHWUVNV9iIYYVNP04IYX01VJjJY]Z^VJkJ[YV^`9Z ^`0@J]YZff[KK]]ZffkkJ]]^nf[lK]]^o6[lK_]_76klKa/2Ka`01WF8iHUUN>@=RF@06IUURNFIJHWUVNV:I0VIj00UVVFJJIYYZVVJjIYYV ^VJkJ[X00VZk00=ZfV[KJ[/00f[K01A^nf[KK_aZffkkK_a[6fkkK_a_6flLLaa_77<0h2;0h0130>;0h/ 3S0>0R`>00@`3R`>;0h`3P8/3P04<0h/3R`><0h2;0h0130>;0h/3S0>0R`>00@`3R`>;0h`3P8/3P04 <0h/3R`><0h2;0h0130>;0h/3S0>0R`>00@`3R`>;0h`3P8/3P04<0h/3R`><0h2;0h0130>;0h/3S0> 0R`>00@`3R`>;0h`3P8/3P04<0h/3R`><0h2;0h0130>;0h/3S0>0R`>00@`3R`>;0h`3P8/3P04<0h/ 3R`><0h2;0h0130>;0h/3S0>0R`>00@`3R`>;0h`3P8/3P04<0h/3R`><0h2;0h0130>;0h/3S0>0R`> 00@`3R`>;0h`3P8/3P05<0l`3S0?<0ld3`03=102>103>342?5400cab@790TP02@9800dBc@;=4d`02 A=<2B?@3BA@04TddBCE==DeDCEEAEDeeDEIAME6FDGIEUU6FEKIE]eFfEKMIeP9Ee`07FMMImeWgFOQI meghFQP015hH0ehh00AR>EiHHUUNF@=RF@9RN@05IWURNVJIIWYVV@03IYX3I[X016ZkI[YZ^f[J0V[K 00YZfV[KJ_]^nf[kK_]^o6lKK_a_6`=_700KLca_?7"], "Graphics", ShowCellBracket->False, CellMargins->{{0, 0}, {Inherited, 0}}, Evaluatable->False, ImageSize->{350, 24}, ImageMargins->{{0, 0}, {0, 0}}, ImageRegion->{{0, 1}, {0, 1}}] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Styles for Headings", "Section"], Cell[CellGroupData[{ Cell[StyleData["Title"], ShowCellBracket->False, CellMargins->{{60, 0}, {0, 5}}, PageBreakBelow->False, LineSpacing->{0, 37}, CounterAssignments->{{"Section", 0}, {"Equation", 0}, {"Figure", 0}}, FontSize->36, FontTracking->"Plain", FontColor->GrayLevel[0]], Cell[StyleData["Title", "Printout"], CellMargins->{{9, 0}, {0, 0}}, FontSize->24, FontTracking->"Plain"] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["Subtitle"], ShowCellBracket->False, CellMargins->{{60, 0}, {0, 5}}, PageBreakBelow->False, LineSpacing->{1, 0}, CounterAssignments->{{"Section", 0}, {"Equation", 0}, {"Figure", 0}}, FontFamily->"Helvetica", FontSize->14, FontSlant->"Italic", FontColor->GrayLevel[0]], Cell[StyleData["Subtitle", "Printout"], CellMargins->{{9, 0}, {0, 0}}, ParagraphIndent->-85, FontSize->16] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["Subsubtitle"], ShowCellBracket->False, CellMargins->{{60, 4}, {30, 10}}, PageBreakBelow->False, CounterAssignments->{{"Section", 0}, {"Equation", 0}, {"Figure", 0}}, FontFamily->"Helvetica", FontSize->12, FontSlant->"Italic"], Cell[StyleData["Subsubtitle", "Printout"], CellMargins->{{9, 10}, {50, 10}}, FontSize->14] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["Section"], CellFrame->{{6, 0}, {0, 1}}, CellDingbat->None, CellMargins->{{44, 0}, {10, 35}}, CellGroupingRules->{"SectionGrouping", 30}, PageBreakBelow->False, CellFrameMargins->{{8, 4}, {0, 4}}, LineSpacing->{0, 22}, CounterIncrements->"Section", CounterAssignments->{{"Subsection", 0}, {"Subsubsection", 0}}, FontFamily->"Helvetica", FontSize->20, FontWeight->"Bold", FontColor->RGBColor[0.571389, 0.19675, 0.570504]], Cell[StyleData["Section", "Printout"], CellMargins->{{9, 0}, {2, 50}}, CellFrameMargins->{{5, 4}, {0, 4}}, FontSize->14, FontTracking->"Plain", FontColor->GrayLevel[0]] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["Subsection"], CellMargins->{{60, 0}, {8, 10}}, CellGroupingRules->{"SectionGrouping", 40}, PageBreakBelow->False, CounterIncrements->"Subsection", CounterAssignments->{{"Subsubsection", 0}}, FontFamily->"Helvetica", FontSize->16, FontWeight->"Bold"], Cell[StyleData["Subsection", "Printout"], CellMargins->{{9, 0}, {6, 40}}, FontSize->12] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["Subsubsection"], CellDingbat->"\[FilledSquare]", CellMargins->{{60, Inherited}, {8, 12}}, CellGroupingRules->{"SectionGrouping", 50}, PageBreakBelow->False, CellFrameLabelMargins->6, CounterIncrements->"Subsubsection", FontFamily->"Times", FontSize->13, FontWeight->"Bold"], Cell[StyleData["Subsubsection", "Printout"], CellMargins->{{22, 0}, {4, 20}}, FontSize->11] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Styles for Body Text", "Section"], Cell[CellGroupData[{ Cell[StyleData["Text"], CellMargins->{{60, 20}, {10, 5}}, LineSpacing->{1, 0}, ParagraphSpacing->{0, 12}, FontFamily->"Times"], Cell[StyleData["Text", "Printout"], CellMargins->{{9, 0}, {4, 4}}, ParagraphSpacing->{0, 6}] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["Commentary"], CellMargins->{{60, 20}, {2, 8}}, PageBreakBelow->False, TextJustification->1, LineSpacing->{1, 2}, FontFamily->"Helvetica", FontSize->10, FontColor->RGBColor[0, 0, 0.4]], Cell[StyleData["Commentary", "Printout"], CellMargins->{{9, 0}, {4, 4}}, LineSpacing->{1, 3}, FontSize->8] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Styles for Input/Output", "Section"], Cell["\<\ The cells in this section define styles used for input and output \ to the kernel. Be careful when modifying, renaming, or removing these \ styles, because the front end associates special meanings with these style \ names.\ \>", "Text"], Cell[CellGroupData[{ Cell[StyleData["Input"], CellFrame->{{3, 0}, {0, 0}}, CellMargins->{{60, 20}, {0, 0}}, Evaluatable->True, CellGroupingRules->"InputGrouping", CellHorizontalScrolling->True, PageBreakWithin->False, GroupPageBreakWithin->False, CellLabelMargins->{{23, Inherited}, {Inherited, Inherited}}, CellFrameColor->RGBColor[0.6, 0.2, 0], DefaultFormatType->DefaultInputFormatType, AutoItalicWords->{}, FormatType->InputForm, ShowStringCharacters->True, NumberMarks->True, CounterIncrements->"Input", FontWeight->"Bold", Background->RGBColor[1, 0.700008, 0.4]], Cell[StyleData["Input", "Printout"], CellFrame->False, CellMargins->{{37, 0}, {6, 6}}, Background->GrayLevel[0.8]] }, Closed]], Cell[StyleData["InlineInput"], Evaluatable->True, CellGroupingRules->"InputGrouping", CellHorizontalScrolling->True, PageBreakWithin->False, GroupPageBreakWithin->False, DefaultFormatType->DefaultInputFormatType, AutoItalicWords->{}, FormatType->InputForm, ShowStringCharacters->True, NumberMarks->True, CounterIncrements->"Input", FontWeight->"Bold"], Cell[CellGroupData[{ Cell[StyleData["Output"], CellFrame->{{3, 0}, {0, 0}}, CellMargins->{{60, 20}, {15, 0}}, CellEditDuplicate->True, CellGroupingRules->"OutputGrouping", CellHorizontalScrolling->True, PageBreakWithin->False, GroupPageBreakWithin->False, GeneratedCell->True, CellAutoOverwrite->True, CellLabelMargins->{{23, Inherited}, {Inherited, Inherited}}, CellFrameColor->RGBColor[0, 0.500008, 0.6], DefaultFormatType->DefaultOutputFormatType, AutoItalicWords->{}, FormatType->InputForm, CounterIncrements->"Output", Background->RGBColor[1, 0.900008, 0.900008]], Cell[StyleData["Output", "Printout"], CellFrame->False, CellMargins->{{37, 0}, {6, 2}}, Background->GrayLevel[0.900008]] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["Graphics"], CellFrame->{{3, 0}, {0, 0}}, CellMargins->{{60, 20}, {0, 0}}, CellGroupingRules->"GraphicsGrouping", CellHorizontalScrolling->True, PageBreakWithin->False, GeneratedCell->True, CellAutoOverwrite->True, ShowCellLabel->False, CellFrameColor->RGBColor[0, 0.6, 0.6], DefaultFormatType->DefaultOutputFormatType, FormatType->InputForm, CounterIncrements->"Graphics", ImageSize->{250, 250}, Background->RGBColor[1, 0.900008, 0.900008]], Cell[StyleData["Graphics", "Printout"], CellFrame->False, CellMargins->{{37, 0}, {6, 2}}, ImageSize->{250, 250}, ImageMargins->{{28, Inherited}, {Inherited, 0}}] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["Message"], CellMargins->{{72, 20}, {Inherited, Inherited}}, CellGroupingRules->"OutputGrouping", PageBreakWithin->False, GroupPageBreakWithin->False, GeneratedCell->True, CellAutoOverwrite->True, ShowCellLabel->False, CellLabelMargins->{{23, Inherited}, {Inherited, Inherited}}, DefaultFormatType->DefaultOutputFormatType, FormatType->InputForm, StyleMenuListing->None, FontColor->RGBColor[1, 0, 0]], Cell[StyleData["Message", "Printout"], CellMargins->{{44, Inherited}, {Inherited, Inherited}}, FontColor->GrayLevel[0]] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["Print"], CellMargins->{{72, 20}, {Inherited, Inherited}}, CellGroupingRules->"OutputGrouping", CellHorizontalScrolling->True, PageBreakWithin->False, GroupPageBreakWithin->False, GeneratedCell->True, CellAutoOverwrite->True, ShowCellLabel->False, CellLabelMargins->{{23, Inherited}, {Inherited, Inherited}}, DefaultFormatType->DefaultOutputFormatType, FormatType->InputForm, StyleMenuListing->None], Cell[StyleData["Print", "Printout"], CellMargins->{{44, Inherited}, {Inherited, Inherited}}] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["CellLabel"], StyleMenuListing->None, FontFamily->"Helvetica", FontSize->9, FontWeight->"Plain", FontSlant->"Italic", FontTracking->"Extended", FontColor->RGBColor[0.571389, 0.19675, 0.570504]], Cell[StyleData["CellLabel", "Printout"], FontFamily->"Courier", FontSize->8, FontSlant->"Italic", FontColor->GrayLevel[0]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Unique Styles", "Section"], Cell[CellGroupData[{ Cell[StyleData["DisplayText"], CellFrame->0.5, CellMargins->{{60, 20}, {15, 5}}, LineSpacing->{0, 12}, ParagraphSpacing->{0, 6}, FontFamily->"Helvetica", FontSize->12, FontWeight->"Bold", FontSlant->"Plain", Background->RGBColor[1, 1, 0.8]], Cell[StyleData["DisplayText", "Printout"], CellMargins->{{9, 0}, {4, 4}}, ParagraphSpacing->{0, 6}, FontSize->10, Background->GrayLevel[0.900008]] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["PictureGroup"], CellFrame->{{3, 0}, {0, 0}}, CellMargins->{{60, Inherited}, {0, 0}}, CellGroupingRules->"GraphicsGrouping", CellHorizontalScrolling->True, PageBreakWithin->False, ShowCellLabel->False, CellFrameColor->RGBColor[0, 0.6, 0.6], CounterIncrements->"Graphics", ImageSize->{250, 250}, Background->RGBColor[1, 0.900008, 0.900008]], Cell[StyleData["PictureGroup", "Printout"], CellFrame->False, CellMargins->{{37, Inherited}, {6, 2}}, ImageSize->{250, 250}, ImageMargins->{{28, Inherited}, {Inherited, 0}}] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Styles for Headers and Footers", "Section"], Cell[StyleData["Header"], CellMargins->{{0, 0}, {4, 1}}, StyleMenuListing->None, FontFamily->"Helvetica", FontSize->9, FontSlant->"Italic"], Cell[StyleData["Footer"], CellMargins->{{0, 0}, {0, 4}}, StyleMenuListing->None, FontFamily->"Helvetica", FontSize->6], Cell[StyleData["PageNumber"], CellMargins->{{0, 0}, {4, 1}}, StyleMenuListing->None, FontFamily->"Helvetica", FontSize->9, FontWeight->"Bold"] }, Closed]], Cell[CellGroupData[{ Cell["Palette Styles", "Section"], Cell["\<\ The cells below define styles that define standard \ ButtonFunctions, for use in palette buttons.\ \>", "Text"], Cell[StyleData["Paste"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`NotebookApply[ FrontEnd`InputNotebook[ ], #, After]}]&)}], Cell[StyleData["Evaluate"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`NotebookApply[ FrontEnd`InputNotebook[ ], #, All], SelectionEvaluate[ FrontEnd`InputNotebook[ ], All]}]&)}], Cell[StyleData["EvaluateCell"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`NotebookApply[ FrontEnd`InputNotebook[ ], #, All], FrontEnd`SelectionMove[ FrontEnd`InputNotebook[ ], All, Cell, 1], FrontEnd`SelectionEvaluateCreateCell[ FrontEnd`InputNotebook[ ], All]}]&)}], Cell[StyleData["CopyEvaluate"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`SelectionCreateCell[ FrontEnd`InputNotebook[ ], All], FrontEnd`NotebookApply[ FrontEnd`InputNotebook[ ], #, All], FrontEnd`SelectionEvaluate[ FrontEnd`InputNotebook[ ], All]}]&)}], Cell[StyleData["CopyEvaluateCell"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`SelectionCreateCell[ FrontEnd`InputNotebook[ ], All], FrontEnd`NotebookApply[ FrontEnd`InputNotebook[ ], #, All], FrontEnd`SelectionEvaluateCreateCell[ FrontEnd`InputNotebook[ ], All]}]&)}] }, Closed]], Cell[CellGroupData[{ Cell["Hyperlink Styles", "Section"], Cell["\<\ The cells below define styles useful for making hypertext \ ButtonBoxes. The \"Hyperlink\" style is for links within the same Notebook, \ or between Notebooks.\ \>", "Text"], Cell[CellGroupData[{ Cell[StyleData["Hyperlink"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, FontColor->RGBColor[0, 0, 1], FontVariations->{"Underline"->True}, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`NotebookLocate[ #2]}]&), Active->True, ButtonNote->ButtonData}], Cell[StyleData["Hyperlink", "Presentation"]], Cell[StyleData["Hyperlink", "Condensed"]], Cell[StyleData["Hyperlink", "Printout"], FontColor->GrayLevel[0], FontVariations->{"Underline"->False}] }, Closed]], Cell["\<\ The following styles are for linking automatically to the on-line \ help system.\ \>", "Text"], Cell[CellGroupData[{ Cell[StyleData["MainBookLink"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, FontColor->RGBColor[0, 0, 1], FontVariations->{"Underline"->True}, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`HelpBrowserLookup[ "MainBook", #]}]&), Active->True, ButtonFrame->"None"}], Cell[StyleData["MainBookLink", "Presentation"]], Cell[StyleData["MainBookLink", "Condensed"]], Cell[StyleData["MainBookLink", "Printout"], FontColor->GrayLevel[0], FontVariations->{"Underline"->False}] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["AddOnsLink"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, FontFamily->"Courier", FontColor->RGBColor[0, 0, 1], FontVariations->{"Underline"->True}, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`HelpBrowserLookup[ "AddOns", #]}]&), Active->True, ButtonFrame->"None"}], Cell[StyleData["AddOnsLink", "Presentation"]], Cell[StyleData["AddOnsLink", "Condensed"]], Cell[StyleData["AddOnLink", "Printout"], FontColor->GrayLevel[0], FontVariations->{"Underline"->False}] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["RefGuideLink"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, FontFamily->"Courier", FontColor->RGBColor[0, 0, 1], FontVariations->{"Underline"->True}, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`HelpBrowserLookup[ "RefGuideLink", #]}]&), Active->True, ButtonFrame->"None"}], Cell[StyleData["RefGuideLink", "Presentation"]], Cell[StyleData["RefGuideLink", "Condensed"]], Cell[StyleData["RefGuideLink", "Printout"], FontColor->GrayLevel[0], FontVariations->{"Underline"->False}] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["GettingStartedLink"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, FontColor->RGBColor[0, 0, 1], FontVariations->{"Underline"->True}, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`HelpBrowserLookup[ "GettingStarted", #]}]&), Active->True, ButtonFrame->"None"}], Cell[StyleData["GettingStartedLink", "Presentation"]], Cell[StyleData["GettingStartedLink", "Condensed"]], Cell[StyleData["GettingStartedLink", "Printout"], FontColor->GrayLevel[0], FontVariations->{"Underline"->False}] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["OtherInformationLink"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, FontColor->RGBColor[0, 0, 1], FontVariations->{"Underline"->True}, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`HelpBrowserLookup[ "OtherInformation", #]}]&), Active->True, ButtonFrame->"None"}], Cell[StyleData["OtherInformationLink", "Presentation"]], Cell[StyleData["OtherInformationLink", "Condensed"]], Cell[StyleData["OtherInformationLink", "Printout"], FontColor->GrayLevel[0], FontVariations->{"Underline"->False}] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Placeholder Styles", "Section"], Cell["\<\ The cells below define styles useful for making placeholder \ objects in palette templates.\ \>", "Text"], Cell[CellGroupData[{ Cell[StyleData["Placeholder"], Editable->False, Selectable->False, StyleBoxAutoDelete->True, Placeholder->True, StyleMenuListing->None], Cell[StyleData["Placeholder", "Presentation"]], Cell[StyleData["Placeholder", "Condensed"]], Cell[StyleData["Placeholder", "Printout"]] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["SelectionPlaceholder"], Editable->False, Selectable->False, StyleBoxAutoDelete->True, Placeholder->Primary, StyleMenuListing->None, DrawHighlighted->True], Cell[StyleData["SelectionPlaceholder", "Presentation"]], Cell[StyleData["SelectionPlaceholder", "Condensed"]], Cell[StyleData["SelectionPlaceholder", "Printout"]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["FormatType Styles", "Section"], Cell["\<\ The cells below define styles that are mixed in with the styles \ of most cells. If a cell's FormatType matches the name of one of the styles \ defined below, then that style is applied between the cell's style and its \ own options.\ \>", "Text"], Cell[StyleData["CellExpression"], PageWidth->Infinity, CellMargins->{{6, Inherited}, {Inherited, Inherited}}, ShowCellLabel->False, ShowSpecialCharacters->False, AllowInlineCells->False, AutoItalicWords->{}, StyleMenuListing->None, FontFamily->"Courier", FontSize->12, Background->GrayLevel[1]], Cell[StyleData["InputForm"], AllowInlineCells->False, StyleMenuListing->None, FontFamily->"Courier"], Cell[StyleData["OutputForm"], PageWidth->Infinity, TextAlignment->Left, LineSpacing->{1, -5}, StyleMenuListing->None, FontFamily->"Courier"], Cell[StyleData["StandardForm"], LineSpacing->{1.25, 0}, StyleMenuListing->None, FontFamily->"Courier"], Cell[StyleData["TraditionalForm"], LineSpacing->{1.25, 0}, SingleLetterItalics->True, TraditionalFunctionNotation->True, DelimiterMatching->None, StyleMenuListing->None], Cell["\<\ The style defined below is mixed in to any cell that is in an \ inline cell within another.\ \>", "Text"], Cell[StyleData["InlineCell"], TextAlignment->Left, ScriptLevel->1, StyleMenuListing->None], Cell[StyleData["InlineCellEditing"], StyleMenuListing->None, Background->RGBColor[1, 0.749996, 0.8]] }, Closed]] }, Open ]] }] ] (*********************************************************************** 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[1709, 49, 112, 4, 82, "Subtitle"], Cell[1824, 55, 77, 0, 58, "Subtitle"], Cell[CellGroupData[{ Cell[1926, 59, 46, 0, 66, "Subsection"], Cell[1975, 61, 64, 1, 55, "Input"], Cell[2042, 64, 320, 6, 199, "Input", Evaluatable->False], Cell[2365, 72, 1168, 18, 463, "Input"], Cell[3536, 92, 161, 3, 44, "Input"], Cell[3700, 97, 1154, 18, 284, "Input"], Cell[4857, 117, 202, 4, 60, "Input"], Cell[5062, 123, 1169, 18, 284, "Input"], Cell[6234, 143, 202, 4, 60, "Input"], Cell[6439, 149, 918, 14, 236, "Input"], Cell[7360, 165, 202, 4, 60, "Input"], Cell[7565, 171, 1107, 18, 284, "Input"], Cell[8675, 191, 213, 4, 60, "Input"], Cell[CellGroupData[{ Cell[8913, 199, 1142, 18, 300, "Input"], Cell[10058, 219, 1090, 17, 70, "Output"] }, Open ]], Cell[11163, 239, 208, 4, 60, "Input"], Cell[CellGroupData[{ Cell[11396, 247, 1142, 18, 463, "Input"], Cell[12541, 267, 1090, 17, 367, "Output"] }, Open ]], Cell[13646, 287, 206, 4, 103, "Input"], Cell[13855, 293, 1150, 18, 463, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[15042, 316, 48, 0, 38, "Subsection"], Cell[15093, 318, 142, 3, 66, "Text"], Cell[15238, 323, 160, 3, 80, "Input"], Cell[15401, 328, 144, 3, 80, "Input"], Cell[15548, 333, 84, 1, 55, "Input"], Cell[15635, 336, 117, 2, 89, "Input"], Cell[15755, 340, 164, 3, 109, "Input"], Cell[15922, 345, 185, 4, 129, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[16144, 354, 38, 0, 38, "Subsection"], Cell[16185, 356, 225, 3, 66, "Text"], Cell[16413, 361, 466, 7, 278, "Input"], Cell[16882, 370, 65, 0, 43, "Text"], Cell[16950, 372, 51, 1, 55, "Input"], Cell[17004, 375, 230, 3, 66, "Text"], Cell[17237, 380, 528, 9, 295, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[17802, 394, 34, 0, 38, "Subsection"], Cell[17839, 396, 58, 0, 43, "Text"], Cell[17900, 398, 76, 1, 55, "Input"], Cell[17979, 401, 49, 1, 55, "Input"], Cell[18031, 404, 322, 7, 89, "Text"], Cell[18356, 413, 160, 3, 80, "Input"], Cell[18519, 418, 247, 3, 66, "Text"], Cell[18769, 423, 68, 1, 55, "Input"], Cell[18840, 426, 77, 1, 55, "Input"], Cell[18920, 429, 49, 0, 43, "Text"], Cell[18972, 431, 133, 2, 103, "Input"], Cell[19108, 435, 145, 3, 66, "Text"], Cell[19256, 440, 61, 1, 55, "Input"], Cell[19320, 443, 92, 3, 43, "Text"], Cell[19415, 448, 82, 1, 55, "Input"], Cell[19500, 451, 68, 0, 43, "Text"], Cell[19571, 453, 115, 2, 79, "Input"], Cell[19689, 457, 450, 6, 112, "Text"], Cell[20142, 465, 122, 2, 79, "Input"], Cell[20267, 469, 179, 3, 66, "Text"], Cell[20449, 474, 99, 2, 55, "Input"], Cell[20551, 478, 87, 1, 55, "Input"], Cell[20641, 481, 98, 3, 43, "Text"], Cell[20742, 486, 126, 2, 79, "Input"], Cell[20871, 490, 192, 4, 66, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[21100, 499, 39, 0, 38, "Subsection"], Cell[21142, 501, 200, 5, 43, "Text"], Cell[21345, 508, 212, 4, 151, "Input"], Cell[21560, 514, 119, 3, 43, "Text"], Cell[21682, 519, 353, 7, 175, "Input"], Cell[22038, 528, 306, 5, 89, "Text"], Cell[CellGroupData[{ Cell[22369, 537, 297, 5, 199, "Input"], Cell[22669, 544, 1097, 17, 281, "Output"] }, Open ]], Cell[23781, 564, 129, 3, 66, "Text"], Cell[23913, 569, 300, 5, 199, "Input"], Cell[24216, 576, 64, 1, 55, "Input"], Cell[24283, 579, 143, 3, 79, "Input"], Cell[24429, 584, 132, 3, 79, "Input"], Cell[24564, 589, 199, 4, 66, "Text"], Cell[24766, 595, 111, 2, 79, "Input"], Cell[24880, 599, 132, 3, 79, "Input"], Cell[25015, 604, 179, 5, 43, "Text"], Cell[25197, 611, 80, 1, 55, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[25314, 617, 38, 0, 38, "Subsection"], Cell[25355, 619, 161, 5, 43, "Text"], Cell[25519, 626, 563, 12, 135, "Text"], Cell[26085, 640, 570, 9, 359, "Input"], Cell[26658, 651, 65, 0, 43, "Text"], Cell[26726, 653, 303, 5, 199, "Input"], Cell[27032, 660, 75, 0, 43, "Text"], Cell[27110, 662, 117, 2, 79, "Input"], Cell[27230, 666, 60, 0, 43, "Text"], Cell[27293, 668, 152, 4, 79, "Input"], Cell[27448, 674, 65, 0, 43, "Text"], Cell[27516, 676, 138, 2, 79, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[27691, 683, 34, 0, 38, "Subsection"], Cell[27728, 685, 531, 17, 89, "Text"], Cell[28262, 704, 947, 16, 415, "Input"], Cell[29212, 722, 36, 0, 43, "Text"], Cell[29251, 724, 303, 5, 199, "Input"], Cell[29557, 731, 51, 0, 43, "Text"], Cell[29611, 733, 121, 2, 79, "Input"], Cell[29735, 737, 68, 0, 43, "Text"], Cell[29806, 739, 152, 4, 79, "Input"], Cell[29961, 745, 75, 0, 43, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[30073, 750, 42, 0, 38, "Subsection"], Cell[30118, 752, 650, 16, 135, "Text"], Cell[30771, 770, 154, 3, 66, "Text"], Cell[30928, 775, 58, 0, 43, "Text"], Cell[30989, 777, 278, 4, 167, "Input"], Cell[31270, 783, 110, 3, 43, "Text"], Cell[31383, 788, 80, 1, 71, "Input"], Cell[31466, 791, 87, 1, 71, "Input"], Cell[31556, 794, 47, 0, 43, "Text"], Cell[31606, 796, 34, 1, 71, "Input"], Cell[31643, 799, 49, 0, 43, "Text"], Cell[31695, 801, 489, 8, 19, "Input", CellOpen->False], Cell[32187, 811, 70, 2, 19, "Input", CellOpen->False], Cell[32260, 815, 547, 10, 19, "Input", CellOpen->False], Cell[32810, 827, 75, 1, 71, "Input"], Cell[32888, 830, 58, 1, 71, "Input"], Cell[32949, 833, 56, 0, 43, "Text"], Cell[33008, 835, 53, 1, 71, "Input"], Cell[33064, 838, 70, 0, 43, "Text"], Cell[33137, 840, 75, 1, 71, "Input"], Cell[33215, 843, 58, 1, 71, "Input"], Cell[33276, 846, 52, 0, 43, "Text"], Cell[33331, 848, 335, 6, 199, "Input"], Cell[33669, 856, 614, 11, 19, "Input", CellOpen->False], Cell[34286, 869, 335, 6, 199, "Input"], Cell[34624, 877, 996, 18, 19, "Input", CellOpen->False], Cell[35623, 897, 335, 6, 199, "Input"], Cell[35961, 905, 136, 2, 95, "Input"], Cell[36100, 909, 101, 3, 43, "Text"], Cell[36204, 914, 140, 2, 95, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[36381, 921, 50, 0, 38, "Subsection"], Cell[36434, 923, 362, 5, 89, "Text"], Cell[36799, 930, 133, 2, 95, "Input"], Cell[36935, 934, 199, 3, 119, "Input"], Cell[37137, 939, 208, 3, 119, "Input"], Cell[37348, 944, 153, 3, 95, "Input"], Cell[37504, 949, 1622, 29, 791, "Input"], Cell[39129, 980, 74, 1, 71, "Input"], Cell[39206, 983, 76, 1, 71, "Input"], Cell[39285, 986, 74, 1, 71, "Input"], Cell[39362, 989, 76, 1, 71, "Input"], Cell[39441, 992, 77, 1, 71, "Input"], Cell[39521, 995, 128, 3, 43, "Text"] }, Closed]] } ] *) (*********************************************************************** End of Mathematica Notebook file. ***********************************************************************)