{VERSION 3 0 "IBM INTEL NT" "3.0" }

{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 

1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 

0 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }

{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "

" 0 21 "" 0 1 0 0 0 1 0 0 0 0 2 0 0 0 0 }{CSTYLE "" -1 256 "Courier" 

0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "Courier" 0 1 0 0 0 

0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "Courier" 0 1 0 0 0 0 0 0 0 0 

0 0 0 0 0 }{CSTYLE "" -1 259 "Courier" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }

{CSTYLE "" -1 260 "Courier" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 

-1 261 "Courier" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 

1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 

0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier

" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }

{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 

0 0 0 0 }1 0 0 0 6 6 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 2" 3 4 1 

{CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 4 4 0 0 

0 0 0 0 -1 0 }{PSTYLE "Heading 3" 4 5 1 {CSTYLE "" -1 -1 "" 1 12 0 0 

0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 }{PSTYLE "" 2 6 

1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 }0 0 0 -1 -1 -1 0 

0 0 0 0 0 -1 0 }{PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 

255 1 0 0 0 0 0 0 1 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Map

le Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }

3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "

" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }

{PSTYLE "Maple Plot" 0 13 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 

0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Title" 0 18 1 

{CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 1 0 0 0 0 0 0 }3 0 0 -1 12 12 0 

0 0 0 0 0 19 0 }{PSTYLE "Author" 0 19 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 

0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 8 8 0 0 0 0 0 0 -1 0 }}

{SECT 0 {PARA 18 "" 0 "" {TEXT -1 38 "Eigenstructure of the Butterfly \+

Scheme" }}{PARA 19 "" 0 "" {TEXT -1 27 "Denis Zorin,  February 1998" }

}{PARA 0 "" 0 "" {TEXT -1 781 "This worksheet contains the symbolic pa

rt of the analysis of  tangen plane continuity and C1-continuity  of  \+

the Butterfly scheme.  We compute the eigenvalues of the subdivision m

atrix with the maximal magnitude  and the corresponding eigenvectors. \+

For the valence K = 3, the largest eigenvalue is 1/4, with 3 Jordan bl

ocks: two of size 2 and one of size 3. For K = 4,5,7 the largest eigen

values are in the first and last blocks of the DFT-transformed matrix,

 and have trivial Jordan blocks.  For K >= 8, the largest eigenvalues \+

are in other blocks. We generate the C-code  for the computationally i

ntensive part of the analysis (analysis of the characteristic maps).  \+

The generated code  uses  functions from our wrapper class for f.p. nu

mbers, encapsulating interval arithmetics." }}{SECT 0 {PARA 3 "" 0 "" 

{TEXT -1 9 "Utilities" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "wit

h(linalg):" }}{PARA 7 "" 1 "" {TEXT -1 32 "Warning, new definition for

 norm" }}{PARA 7 "" 1 "" {TEXT -1 33 "Warning, new definition for trac

e" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "with(plots): " }}}

{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "readlib(realroot):" }}}

{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "with(share):" }}{PARA 6 "" 

1 "" {TEXT -1 70 "See ?share and ?share,contents for information about

 the share library" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "reads

hare(intpak,numerics):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 107 "

### WARNING: the grobner package is obsolete and has been replaced wit

h the Groebner package\nwith(grobner):" }}}{EXCHG {PARA 0 "> " 0 "" 

{MPLTEXT 1 0 18 "readlib(optimize):" }}}{EXCHG {PARA 0 "> " 0 "" 

{MPLTEXT 1 0 37 "readlib(procbody): readlib(procmake):" }}}{EXCHG 

{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "_EnvExplicit := true:" }}}{EXCHG 

{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "readlib(C):" }}}{EXCHG {PARA 0 "> \+

" 0 "" {MPLTEXT 1 0 25 "interface(showassumed=0);" }}}{EXCHG {PARA 0 "

" 0 "" {TEXT -1 52 "Fix the broken convert/interval function from intp

ak" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "read(`subdivmatrix-util.mpl`)

;" }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 18 "Subdivision matrix" }}

{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 110 "assume( c >= -1); additiona

lly( c <= -1); additionally (c, real); assume( K, integer); \naddition

ally( K >= 3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 388 "Butterfl

y := matrix( [ \n [ (1/2) + 4*w*c - 2*w*(2*c^2-1), 0,- w*(conjugate(om

ega) + 1),0,0,0],\n [1,0,0,0,0,0],\n [(1/2)*(1+ omega) - w*(conjugate(

omega) + omega^2 ), -w*(1 + omega),2*w,0,0,0], \n [1/2 - 2*w*c,1/2,2*w

*(1+conjugate(omega)),0, -w, -w*conjugate(omega)],\n [1/2 + 2*w*omega,

 2*w - w*omega,1/2-w*conjugate(omega),0,-w,0], \n [(1/2)*omega + 2*w,2

*w*omega-w, 1/2 - w*omega,0,0,-w]]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "

6#>%*ButterflyG-%'MATRIXG6#7(7(,(#\"\"\"\"\"#F,*&%\"wGF,%#c|irGF,\"\"%

*&F/F,,&*$F0F-F-!\"\"F,F,!\"#\"\"!,$*&F/F,,&-%*conjugateG6#%&omegaGF,F

,F,F,F5F7F7F77(F,F7F7F7F7F77(,(F+F,F>F+*&F/F,,&F;F,*$F>F-F,F,F5,$*&F/F

,,&F,F,F>F,F,F5,$F/F-F7F7F77(,&F+F,F.F6F+,$F9F-F7,$F/F5,$*&F/F,F;F,F57

(,&F+F,*&F/F,F>F,F-,&F/F-FQF5,&F+F,FNF5F7FLF77(,&F>F+F/F-,&FQF-F/F5,&F

+F,FQF5F7F7FL" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 89 "Buttercons

t := \{ w = 1/16\}; Buttervar := \{ omega = exp(2*I*Pi*m/K), c = cos(2

*m*Pi/K) \}; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%,ButterconstG<#/%\"

wG#\"\"\"\"#;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*ButtervarG<$/%#c|i

rG-%$cosG6#,$*(%\"mG\"\"\"%#PiGF.%#K|irG!\"\"\"\"#/%&omegaG-%$expG6#,$

**%\"IGF.F/F.F-F.F0F1F2" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 150 

"ButterflyExpanded :=  map( simplify, subs( s^2 = 1-c^2, map( simplify

, map( evalc, subs( \{ omega = c + s*I , op(Butterconst)\}, eval(Butte

rfly))) )))\n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%2ButterflyExpanded

G-%'MATRIXG6#7(7(,(#\"\"&\"\")\"\"\"%#c|irG#F.\"\"%*$F/\"\"##!\"\"F1\"

\"!,(F/#F5\"#;F8F.*&%\"IGF.%\"sGF.#F.F9F6F6F67(F.F6F6F6F6F67(,,#\"\"*F

9F.F/#\"\"(F9F2#F5F-F:FA*(F;F.F/F.F<F.FE,(F8F.F/F8F:F8#F.F-F6F6F67(,&#

F.F3F.F/FEFK,(F/FHFHF.F:FEF6F8,&F/F8F:F=7(,(FKF.F/FHF:FH,(FHF.F/F8F:F8

,(FKF.F/F8F:F=F6F8F67(,(F/FKF:FKFHF.,(F/FHF:FHF8F.,(FKF.F/F8F:F8F6F6F8

" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 122 "Because the matrix has block

-diagonal structure, we have to compute only the eigenvalues of the su

bblocks on the diagonal." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "Butterf

ly00 := submatrix( ButterflyExpanded, 1..3,1..3):" }}}{EXCHG {PARA 0 "

> " 0 "" {MPLTEXT 1 0 57 "Butterfly11 := submatrix( ButterflyExpanded,

 4..6,4..6): " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "Butterfly1

0 := submatrix( ButterflyExpanded, 4..6,1..3): " }}}{EXCHG {PARA 0 "> \+

" 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 40 "Introd

uce new variables, cs and ss, for " }{XPPEDIT 18 0 "cos(m*Pi/K)" "6#-%

$cosG6#*(%\"mG\"\"\"%#PiGF(%\"KG!\"\"" }{TEXT -1 5 " and " }{XPPEDIT 

18 0 "sin(m*Pi/K)" "6#-%$sinG6#*(%\"mG\"\"\"%#PiGF(%\"KG!\"\"" }{TEXT 

-1 3 " . " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "Cre :=  diag( 1, 1, cs

 - I*ss );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$CreG-%'MATRIXG6#7%7%

\"\"\"\"\"!F+7%F+F*F+7%F+F+,&%#csGF**&%\"IGF*%#ssGF*!\"\"" }}}{EXCHG 

{PARA 0 "" 0 "" {TEXT -1 102 "Reduce the first subblock to a real matr

ix using a coordinate  transoform. Eigenvalues  do not change." }}

{PARA 0 "> " 0 "" {MPLTEXT 1 0 242 "Butter00re :=  map( simplify, subs

( ss^2 = 1- cs^2, map( expand, map( simplify, subs( \{s^2 = 1 - c^2\},

 subs( \{ c = 2*cs^2 - 1, s = 2*cs*ss\},  map(simplify, map( evalc, ma

p( simplify, evalm( Cre &*  eval(Butterfly00) &* inverse(Cre))))))))))

);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%+Butter00reG-%'MATRIXG6#7%7%,(

#\"\"\"\"\")F,*$%#csG\"\"##\"\"$F0*$F/\"\"%!\"\"\"\"!,$F/#F5F-7%F,F6F6

7%,&*$F/F2#F5F0F/#\"#6F-F7F+" }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 43 

"Analysis of the behavior of the eigenvalues" }}{PARA 0 "" 0 "" {TEXT 

-1 400 "Our goal is to determine the expresions for the eigenvalues of

 the largest magnitude, excluding 1, and show that for  valences > 8 t

hese eigenvalues are not in the 1st and last blocks of the DFT-transfo

rmed subdivision matrix.  With some additional easily provable assumpt

ions, this means that the Butterfly scheme is not C1 for these valence

s.   We also explicitly compute the eigenvalues for K = 3." }}{SECT 0 

{PARA 4 "" 0 "" {TEXT -1 10 "0-th block" }}{EXCHG {PARA 0 "" 0 "" 

{TEXT -1 150 "The block corresponding to m = 0 is present in every mat

rix; if the eigenvalues of some other block are greater than  1/4, thi

s block is not dominant." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "jordan(

subs(  cs = 1, eval(Butter00re)));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#

-%'MATRIXG6#7%7%#\"\"\"\"\"%F)\"\"!7%F+F(F)7%F+F+F(" }}}}{SECT 0 

{PARA 4 "" 0 "" {TEXT -1 68 " Characteristic polynomial of the first s

ublock and its descriminant" }}{PARA 0 "" 0 "" {TEXT -1 123 "The eigen

values of the second subblock are 0, and -1/16; we will see that the f

irst subblock always has larger eigenvalues." }}{EXCHG {PARA 0 "" 0 "

" {TEXT -1 25 "Characteristic polynomial" }}{PARA 0 "> " 0 "" 

{MPLTEXT 1 0 123 "ButterCharpoly := subs( cs = sqrt(d), collect( subs(

 cos(m*Pi/K) = c, expand( charpoly(Butter00re,lambda),trig)), lambda))

;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%/ButterCharpolyG,**$%'lambdaG\"

\"$\"\"\"*&,(#!\"\"\"\"%F)*$%\"dG\"\"#F)F0#!\"$F1F)F'F1F)*&,(F0#\"#B\"

#k#F)F8F)F/#F3\"#;F)F'F)F)F0#F-F8" }}}{EXCHG {PARA 0 "> " 0 "" 

{MPLTEXT 1 0 120 "re := coeff( ButterCharpoly, lambda^2); se := coeff(

 ButterCharpoly, lambda); te := rem(ButterCharpoly, lambda, lambda);" 

}}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#reG,(#!\"\"\"\"%\"\"\"*$%\"dG\"\"

#F)F+#!\"$F," }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#seG,(%\"dG#\"#B\"#k

#\"\"\"F)F+*$F&\"\"##!\"$\"#;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#te

G,$%\"dG#!\"\"\"#k" }}}{PARA 4 "" 0 "" {TEXT -1 1 " " }}{EXCHG {PARA 

0 "" 0 "" {TEXT -1 44 "Reduce the characteristic polynomial;  use  " }

{XPPEDIT 18 0 "d = c^2" "6#/%\"dG*$%\"cG\"\"#" }{TEXT -1 18 " as the p

arameter." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 91 "ButterCharpolyReduced \+

:= collect(simplify(subs( lambda = mu - re/3, ButterCharpoly)), mu); \+

" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%6ButterCharpolyReducedG,4*$%#muG

\"\"$\"\"\"*&,,#!\"\"\"$#>F)*$%\"dGF(F)*$F0\"\"##!#P\"#[F0#\"\"(\"#k*$

F0\"\"%#F-F(F)F'F)F)F0#F)\"$o(F1#\"#b\"%_6F9#\"#t\"$W\"F/#!#>F8*$F0\"

\"'#F2\"#F*$F0\"\"&F;#F)\"%7pF)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 

1 0 80 "pe := coeff(ButterCharpolyReduced, mu); qe := rem(ButterCharpo

lyReduced, mu,mu);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#peG,,#!\"\"\"

$#>\"\"\"*$%\"dG\"\"$F)*$F+\"\"##!#P\"#[F+#\"\"(\"#k*$F+\"\"%#F'F," }}

{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#qeG,0%\"dG#\"\"\"\"$o(*$F&\"\"##\"#

b\"%_6*$F&\"\"%#\"#t\"$W\"*$F&\"\"$#!#>\"#k*$F&\"\"'#F+\"#F*$F&\"\"&#!

\"\"F5#F(\"%7pF(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 46 "Find the disc

riminant and deterimine its sign." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 

40 "Discr := simplify( (pe/3)^3 + (qe/2)^2);" }}{PARA 11 "" 1 "" 

{XPPMATH 20 "6#>%&DiscrG,2%\"dG#\"\"\"\"('HfB*$F&\"\"##!#>\"(W*QN*$F&

\"\"%#!$z%\"'oBW*$F&\"\"$#\"%B6\"())y2(*$F&\"\"'#!%p8F3*$F&\"\"&#\"$*H

\"'#f5\"*$F&\"\"(#\"#\"*\"&'Hb*$F&\"\")#!\"\"\"%sI" }}}{EXCHG {PARA 0 

"" 0 "" {TEXT -1 1 " " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "Discr := f

actor(subs( w = 1/16, Discr));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&D

iscrG,$**%\"dG\"\"\",&F'\"\"%!\"\"F(F(,,*$F'F*\"$w&*$F'\"\"$!%;;*$F'\"

\"#\"$w*F'!#?F0F(F(,&F'F(F+F(F3#F+\"())y2(" }}}{EXCHG {PARA 0 "> " 0 "

" {MPLTEXT 1 0 22 "plot(Discr, d = 0..1);" }}{PARA 13 "" 1 "" 

{GLPLOT2D 548 340 340 {PLOTDATA 2 "6%-%'CURVESG6$7^o7$\"\"!F(7$$\"1nmm

;arz@!#<$\"1@SKk-r*4)!#C7$$\"1LL$e9ui2%F,$\"1iYJxdRS;!#B7$$\"1nmm\"z_

\"4iF,$\"1s8x*)f'H)HF57$$\"1mmmT&phN)F,$\"1\"e``@m>x%F57$$\"1LLe*=)H\\

5!#;$\"1_\"z7lY))y'F57$$\"1nm\"z/3uC\"FC$\"1%p^\"*)\\k(e)F57$$\"1++DJ$

RDX\"FC$\"186y#egX+\"!#A7$$\"1LLekGhe:FC$\"1&)*4f]dD0\"FP7$$\"1nm\"zR'

ok;FC$\"1c@+h%ee2\"FP7$$\"1LL3_(>/x\"FC$\"1M^ZrBHq5FP7$$\"1++D1J:w=FC$

\"1M5IYH;K5FP7$$\"1n;HdG\"\\)>FC$\"1M&[:F_Vb*F57$$\"1LLL3En$4#FC$\"1Ca

cx'phP)F57$$\"1nm;/RE&G#FC$\"1m#Hfu-*H_F57$$\"1+++D.&4]#FC$!1!*G2T()o?

F!#D7$$\"1+++vB_<FFC$!12GX(><#\\rF57$$\"1+++v'Hi#HFC$!1HFxG%[yc\"FP7$$

\"1nm\"z*ev:JFC$!1AzYtT\"*pCFP7$$\"1LLL347TLFC$!1:V:MNFuOFP7$$\"1LLLLY

.KNFC$!1Mf())>\"**yZFP7$$\"1++D\"o7Tv$FC$!10\"o77PC7'FP7$$\"1LLL$Q*o]R

FC$!1P?Uei1FtFP7$$\"1++D\"=lj;%FC$!1+U9;6x@')FP7$$\"1++vV&R<P%FC$!1o9]

OXp'y*FP7$$\"1LL$e9Ege%FC$!1EoW[r#))3\"!#@7$$\"1LLeR\"3Gy%FC$!1<XIKOBw

6Ffs7$$\"1nm;/T1&*\\FC$!1eabXCQ_7Ffs7$$\"1mm\"zRQb@&FC$!1!))*R>%f%38Ff

s7$$\"1LLLe,]6`FC$!1cvEzr)[K\"Ffs7$$\"1***\\(=>Y2aFC$!1r,U\"QXiL\"Ffs7

$$\"1mT&Qe#GfaFC$!1+&4O+I-M\"Ffs7$$\"1L$e*[K56bFC$!1x!\\Q*)*oU8Ffs7$$

\"1+D19R#Hc&FC$!1Q[1$H:OM\"Ffs7$$\"1mm;zXu9cFC$!1mXDu(**HM\"Ffs7$$\"1L

Le9i\"=s&FC$!1^Oc+w$oL\"Ffs7$$\"1+++]y))GeFC$!1'=%3:p5C8Ffs7$$\"1***\\

ibOO$fFC$!1%)4-`SP08Ffs7$$\"1****\\i_QQgFC$!1%yB))\\m0G\"Ffs7$$\"1***

\\7y%3TiFC$!1zcTm+2;7Ffs7$$\"1****\\P![hY'FC$!1x?fz%>67\"Ffs7$$\"1LLL$

Qx$omFC$!122!*)zTy,\"Ffs7$$\"1+++v.I%)oFC$!1oEdq#Ry#*)FP7$$\"1mm\"zpe*

zqFC$!1\\`G`jA-xFP7$$\"1+++D\\'QH(FC$!1/E*)H:=5jFP7$$\"1KLe9S8&\\(FC$!

1\"*yD\"4\"R)*\\FP7$$\"1***\\i?=bq(FC$!1a0RAobwOFP7$$\"1LLL3s?6zFC$!1z

Kv6\"[;[#FP7$$\"1++DJXaE\")FC$!1*)oOy4B#Q\"FP7$$\"1nmmm*RRL)FC$!1q;Q7r

7$4&F57$$\"1mm;a<.Y&)FC$\"1?@tH#euk\"F57$$\"1+]PM&*>^')FC$\"1:a%Rx=R6%

F57$$\"1LLe9tOc()FC$\"1Y)4>%*Q)*)fF57$$\"1m;H#e0I&))FC$\"17wmV!f))>(F5

7$$\"1+++]Qk\\*)FC$\"1:6)Qq[,$zF57$$\"1L$3-.B]+*FC$\"10,po'*3V\")F57$$

\"1nmT5ASg!*FC$\"1n()3FSN8#)F57$$\"1+]i!R\"y:\"*FC$\"1:$)=`6N[\")F57$$

\"1LL$3dg6<*FC$\"13(*GuorczF57$$\"1++voTAq#*FC$\"1=E&y<r+L(F57$$\"1mmm

mxGp$*FC$\"185aV/*zR'F57$$\"1++D\"oK0e*FC$\"1MPr/\"=[y$F57$$\"1+++]oi

\"o*FC$\"1XPt<RwnCF57$$\"1++v=5s#y*FC$\"1tX]<,y!H\"F57$$\"1+]P40O\"*)*

FC$\"1i')=M\"4#GOF/7$$\"\"\"F(F(-%'COLOURG6&%$RGBG$\"#5!\"\"F(F(-%+AXE

SLABELSG6$%\"dG%!G-%%VIEWG6$;F(F[`l%(DEFAULTG" 1 2 0 1 0 2 9 1 4 2 

1.000000 45.000000 45.000000 0 }}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 70 

"Pull out the degree 4 factor responcible for one of the roots on 0..1

 " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 1 " " }

{MPLTEXT 1 0 65 "DiscrFactor4 := factor(Discr/(lcoeff(Discrs)*(d-1/4)*

(d-1)^2*d));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%-DiscrFactor4G,,*$%

\"dG\"\"%#!\"\"\"%sI*$F'\"\"$#\"$,\"\"'#f5\"*$F'\"\"##!#hF0F'#\"\"&\"'

oBW#F*\"'C)*e\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "plot

(DiscrFactor4, d=0..1);" }}{PARA 13 "" 1 "" {GLPLOT2D 316 236 236 

{PLOTDATA 2 "6%-%'CURVESG6$7S7$\"\"!$!1WW%p+@ap\"!#@7$$\"1nmm;arz@!#<$

!1I,-@0t,<F+7$$\"1LL$e9ui2%F/$!1u%)p%RI-4#F+7$$\"1nmm\"z_\"4iF/$!1;26.

^N1HF+7$$\"1mmmT&phN)F/$!1*o'4K.O&3%F+7$$\"1LLe*=)H\\5!#;$!1#flEz)ymbF

+7$$\"1nm\"z/3uC\"FD$!1*pa$)**\\V<(F+7$$\"1++DJ$RDX\"FD$!1'*o-v(\\s.*F

+7$$\"1nm\"zR'ok;FD$!1F`::,g86!#?7$$\"1++D1J:w=FD$!18vdq;AO8FV7$$\"1LL

L3En$4#FD$!1,OKG/6v:FV7$$\"1nm;/RE&G#FD$!1Hw?'HZ1z\"FV7$$\"1+++D.&4]#F

D$!1tRs-ZeN?FV7$$\"1+++vB_<FFD$!1[;^5MY!G#FV7$$\"1+++v'Hi#HFD$!1]J^eg<

7DFV7$$\"1nm\"z*ev:JFD$!1J/T#fAkr#FV7$$\"1LLL347TLFD$!1(\\[+j='[HFV7$$

\"1LLLLY.KNFD$!1$Hq8uuQ8$FV7$$\"1++D\"o7Tv$FD$!1I!pGXOML$FV7$$\"1LLL$Q

*o]RFD$!1***4-s#e$\\$FV7$$\"1++D\"=lj;%FD$!1CAk[(R\"\\OFV7$$\"1++vV&R<

P%FD$!1//*)pshvPFV7$$\"1LL$e9Ege%FD$!11C@Rl-$)QFV7$$\"1LLeR\"3Gy%FD$!1

RWT1a#z&RFV7$$\"1nm;/T1&*\\FD$!1qwz8df6SFV7$$\"1mm\"zRQb@&FD$!1&\\f[;(

)e.%FV7$$\"1***\\(=>Y2aFD$!1**Qh6VqHSFV7$$\"1mm;zXu9cFD$!1Og_wiJ$*RFV7

$$\"1+++]y))GeFD$!1F=![jUA#RFV7$$\"1****\\i_QQgFD$!1`c`%GU)=QFV7$$\"1*

**\\7y%3TiFD$!1L5%Hiuho$FV7$$\"1****\\P![hY'FD$!1efd@]e+NFV7$$\"1LLL$Q

x$omFD$!1TL.OO**)H$FV7$$\"1+++v.I%)oFD$!1!)=Ps%=q/$FV7$$\"1mm\"zpe*zqF

D$!1ne`&yudy#FV7$$\"1+++D\\'QH(FD$!1'3T#fILkCFV7$$\"1KLe9S8&\\(FD$!1Ia

&p1>y7#FV7$$\"1***\\i?=bq(FD$!1*=-3!*H5u\"FV7$$\"1LLL3s?6zFD$!1)3***3g

lG8FV7$$\"1++DJXaE\")FD$!1%3CIIOGh)F+7$$\"1nmmm*RRL)FD$!1@@USW!Rx$F+7$

$\"1mm;a<.Y&)FD$\"1')yM!=P#3:F+7$$\"1LLe9tOc()FD$\"1'*)y%zXVpqF+7$$\"1

+++]Qk\\*)FD$\"1#zNJ/z_C\"FV7$$\"1LL$3dg6<*FD$\"1:GW,K2$*=FV7$$\"1mmmm

xGp$*FD$\"1>p+`+)*)\\#FV7$$\"1++D\"oK0e*FD$\"1c>UEv(4<$FV7$$\"1++v=5s#

y*FD$\"1\"*ydhMjPQFV7$$\"\"\"F($\"10+v=njxXFV-%'COLOURG6&%$RGBG$\"#5!

\"\"F(F(-%+AXESLABELSG6$%\"dG%!G-%%VIEWG6$;F(Fez%(DEFAULTG" 1 2 0 1 0 

2 9 1 4 2 1.000000 45.000000 45.000000 0 }}}}{EXCHG {PARA 0 "" 0 "" 

{TEXT -1 25 "Find the interesting root" }}{PARA 0 "> " 0 "" {MPLTEXT 

1 0 61 "DiscrRoot := solve( \{ DiscrFactor4 = 0, d <= 1, d >= 0\},d );

 " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%*DiscrRootG<#/%\"dG,(#\"$,\"\"$

W\"\"\"\"*$*&,(*$,&\")9818F,*$\"'<!H##F,\"\"#\"%Q_#F,\"\"$\"%XV*$F1#F6

F9\"#7\"'kslF,F,F1#!\"\"F9F5#F,F+*$*(,**&F1F8F.F5\"%!p)*&F.F5F1F<!#7F-

!'kslF0\"'a@JF,F1F?F.#F@F6F5#F@F+" }}}{EXCHG {PARA 0 "> " 0 "" 

{MPLTEXT 1 0 33 "DiscrRoot := op(2,op(DiscrRoot));" }}{PARA 12 "" 1 "

" {XPPMATH 20 "6#>%*DiscrRootG,(#\"$,\"\"$W\"\"\"\"*$*&,(*$,&\")9818F)

*$\"'<!H##F)\"\"#\"%Q_#F)\"\"$\"%XV*$F.#F3F6\"#7\"'kslF)F)F.#!\"\"F6F2

#F)F(*$*(,**&F.F5F+F2\"%!p)*&F+F2F.F9!#7F*!'kslF-\"'a@JF)F.F<F+#F=F3F2

#F=F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "evalf(DiscrRoot);

" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+R?\"o[)!#5" }}}{EXCHG {PARA 0 

"" 0 "" {TEXT -1 306 "We observe that the discriminant has four roots:

 0,1, 1/4 and approx. 0.8486812039; these are the only values for whic

h the matrix may have nontrivial Jordan blocks.  The last case does no

t occur in the cases which are of interest to us.  In the first 3 case

s the Jordan normal form can be find explicitly." }}}}{SECT 0 {PARA 4 

"" 0 "" {TEXT -1 29 " The case of three real roots" }}{EXCHG {PARA 0 "

" 0 "" {TEXT -1 89 " The discriminant is positive on  0..1/4 and on  D

iscrRoot..1, negative on 1/4..DiscrRoot" }}}{EXCHG {PARA 0 "" 0 "" 

{TEXT -1 96 "Compute the solutions when the discriminant is negative a

nd, therefore, there are 3  real roots " }}{PARA 0 "> " 0 "" {MPLTEXT 

1 0 26 "R :=  sqrt(-factor(pe)/3):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 

27 "phi := arccos( qe/(2*R^3)):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 

1 0 105 "r1 := -2*R*cos(phi/3)-re/3: r2 :=  -2*R*cos(phi/3 + 2*Pi/3)-r

e/3: r3 :=  -2*R*cos(phi/3 + 4*Pi/3)-re/3:  " }}}{EXCHG {PARA 0 "" 0 "

" {TEXT -1 154 "The product of the roots is  -d/64, which is negative;

 therefore, either all three are positive, or two are negative. 0 is n

ever a root, except when d = 0" }}{PARA 0 "" 0 "" {TEXT -1 274 " The r

oots cannot be equal on the interval where the discriminant does not c

hange sign; we can figure out the largest one on the whole interval by

 evaluating them at a single value of d. We conclude that all three ro

ots are always positive and the largest one is the second." }}{PARA 0 

"" 0 "" {TEXT -1 76 "d = 1/4..DiscrRoot.  We use interval arithmetics \+

to  guarantee correctness. " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "Inve

rvalRoots := map( unapply('inapply'(x,d),x), [r1,r2,r3] ):" }}}{EXCHG 

{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "eval(InvervalRoots(1/2));" }}{PARA 

11 "" 1 "" {XPPMATH 20 "6#7%7$$\"+HF&)*\\)!#6$\"+hR&)*\\)F'7$$\"+&=:/p

%!#5$\"+f_T!p%F-7$$\"+g$*ff>F-$\"+I&*ff>F-" }}}{EXCHG {PARA 0 "" 0 "" 

{TEXT -1 48 "We conclude that te second root is the largest. " }}

{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "AbsDominantEV1 := r2;" }}{PARA 11 "

" 1 "" {XPPMATH 20 "6#>%/AbsDominantEV1G,**&*&,&%\"dG\"\"\"!\"\"F*F*,*

*$F)\"\"$\"#k*$F)\"\"#!$G\"F)\"#?F+F*F*#F*F1-%$sinG6#,&-%'arccosG6#,$*

&,0F)#F*\"$o(F0#\"#b\"%_6*$F)\"\"%#\"#t\"$W\"F-#!#>F/*$F)\"\"'#F1\"#F*

$F)\"\"&#F+F.#F*\"%7pF*F*F'#!\"$F1FS#F*F.%#PiG#F*FLF*#F*\"#7FYF*F0FQF)

F4" }}}{EXCHG {PARA 11 "" 1 "" {XPPMATH 20 "6#7%7$$\"+*p_)*\\)!#6$\"+r

R&)*\\)F'7$$\"+%=:/p%!#5$\"+g_T!p%F-7$$\"+c$*ff>F-$\"+L&*ff>F-" }}}

{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "plot( [r1, r2, r3], d = 1/4.

.DiscrRoot);" }}{PARA 13 "" 1 "" {GLPLOT2D 544 280 280 {PLOTDATA 2 "6'

-%'CURVESG6$7U7$$\"1+++++++D!#;$\"1.+++++]i!#<7$$\"1R4)\\Y&\\IEF*$\"14

m[ML?ejF-7$$\"1%R08()QSu#F*$\"1nX/Ubr^kF-7$$\"1/9&oII<(GF*$\"1!['>FDbc

lF-7$$\"1^(>T;o-+$F*$\"1uE3<t3imF-7$$\"1S)*Q.^>GJF*$\"14;.]\"[uw'F-7$$

\"1*H\")=v*zYKF*$\"1-^H2xnloF-7$$\"1^[a&*zgpLF*$\"11_5Aa<opF-7$$\"102#

oX;m\\$F*$\"1fv&e*3DvqF-7$$\"1v/N+w@BOF*$\"10Opo=H$=(F-7$$\"1`%HxVUMv$

F*$\"1Nv!f6:gH(F-7$$\"1:dPXX9oQF*$\"1sbIQ[\"oR(F-7$$\"1(4l9&>F(*RF*$\"

1(3I'yF=7vF-7$$\"1(=!4n&Hp7%F*$\"1cXfHcCIwF-7$$\"11pr/(y=D%F*$\"1p*4q-

Fju(F-7$$\"1vK-#\\W`O%F*$\"1L_Ud`'Q&yF-7$$\"1ikx(Gm-]%F*$\"1FqZ')>e%)z

F-7$$\"1&\\+luiXh%F*$\"1ze?(p5z4)F-7$$\"12qe*p;vu%F*$\"1zu#Q$p&HB)F-7$

$\"1[*[iZ._'[F*$\"1l7[OGeb$)F-7$$\"1#z(fAXK%*\\F*$\"1s:BCJp$\\)F-7$$\"

1([*=$Hys6&F*$\"1'3I>r8*G')F-7$$\"1xV5awcX_F*$\"17#G*)QBTx)F-7$$\"1q%G

]LxLO&F*$\"1MM,'zD9\"*)F-7$$\"1u,W\"*4X!\\&F*$\"1pn<;s0k!*F-7$$\"1G902

[WAcF*$\"1*H\\i#H#zA*F-7$$\"1b1c6eMPdF*$\"1$\\a<+#Hv$*F-7$$\"1*\\YU/U9

'eF*$\"1=vke#Q(R&*F-7$$\"1#3OafX'*)fF*$\"1!=b#Gqz:(*F-7$$\"1=bcex1:hF*

$\"1U1t+gb%*)*F-7$$\"1=2[],UOiF*$\"1$[a;#>T25F*7$$\"1Bho\"Hh6P'F*$\"1B

M')\\8<G5F*7$$\"1JN\"**>KA\\'F*$\"1j'>-&HiZ5F*7$$\"1AU^O7]@mF*$\"1V/$[

s)Hp5F*7$$\"1E5$o>Q'QnF*$\"1tjWq'>)*3\"F*7$$\"1$)HQM)*pmoF*$\"17)y@p+L

6\"F*7$$\"1*eU_&e>()pF*$\"1+tQo')[O6F*7$$\"1>6R;*[J6(F*$\"1/>mC-)>;\"F

*7$$\"1etyb5HOsF*$\"1B!=uxz#)=\"F*7$$\"16d^j%4_O(F*$\"1Ez$\\p_u@\"F*7$

$\"1EVZ7KP*[(F*$\"1L[()*z]tC\"F*7$$\"1H@:z&[jh(F*$\"1x#=s\\M+G\"F*7$$

\"1g`oDDFUxF*$\"1Y)>_G?\\J\"F*7$$\"1JUfaN)z&yF*$\"1[\"e>6z&\\8F*7$$\"1

6nq^9g!*zF*$\"1;t\"3JEJR\"F*7$$\"1UN$)zk@4\")F*$\"1;*3(H\\hO9F*7$$\"1X

ShR[oN#)F*$\"14SZkc&)*[\"F*7$$\"1l&o#=!3iH)F*$\"1(pV:!49>:F*7$$\"1%3Bp

>JnN)F*$\"1=k\"*yaU_:F*7$$\"1U:'zhr<U)F*$\"1AW4O*Gjf\"F*7$$\"1+++R?\"o

[)F*$\"1PMMQRl)o\"F*-%'COLOURG6&%$RGBG$\"#5!\"\"\"\"!Fi[l-F$6$7U7$F($

\"1^ki=+++DF*7$$\"1q/\\KxClDF*$\"1o8$)z%HKt#F*7$F/$\"1[*pSUg*[GF*7$$\"

1nJ9orE(o#F*$\"1$poeDFO$HF*7$F4$\"1(\\?&>2D5IF*7$F9$\"1eT[*R()[;$F*7$F

>$\"19t(H[zZI$F*7$FC$\"1Vs-d/NLMF*7$FH$\"1>I)QV3_a$F*7$FM$\"1>o1uK\"[l

$F*7$FR$\"1x0z*[NBw$F*7$FW$\"1*[P\"y0=kQF*7$Ffn$\"1;%o$oU!Q'RF*7$F[o$

\"1/`HOD[ZSF*7$F`o$\"1=,U*yDt8%F*7$Feo$\"1Y+fF\\0BUF*7$Fjo$\"1Vv>w1a,V

F*7$F_p$\"1V9*Qhw$pVF*7$Fdp$\"1l$*)yjbeW%F*7$Fip$\"1'3Q9WLr]%F*7$F^q$

\"1<zv(*oSuXF*7$Fcq$\"1#HWGd(QIYF*7$Fhq$\"1:Whhc(zo%F*7$F]r$\"1(fU8^,

\"RZF*7$Fbr$\"1p21Hcf)y%F*7$Fgr$\"1nB!)3oeI[F*7$F\\s$\"1OrKlc;s[F*7$Fa

s$\"14!p!4rE6\\F*7$Ffs$\"1g`Jhe!>%\\F*7$F[t$\"1q'38ZI9(\\F*7$F`t$\"1))

>%[\"f-)*\\F*7$Fet$\"17\\Qb8=?]F*7$Fjt$\"1A=!*yu&z.&F*7$F_u$\"1&zq%pXW

`]F*7$Fdu$\"1o$=<H7N1&F*7$Fiu$\"1CuL_.?q]F*7$F^v$\"15O)p5*fs]F*7$Fcv$

\"1vge#*))=r]F*7$Fhv$\"1K7qdQ'f1&F*7$F]w$\"1<dH\">+k0&F*7$Fbw$\"1?JI;#

GH/&F*7$Fgw$\"1x9]+TPC]F*7$F\\x$\"1[YWn\"4@+&F*7$Fax$\"1w%>vjsZ(\\F*7$

Ffx$\"1GIY.\"zH%\\F*7$F[y$\"1`2=,>`4\\F*7$F`y$\"1rgH*fXg'[F*7$Fey$\"1W

1Q4jJA[F*7$Fjy$\"1.d)z)eWqZF*7$Fdz$\"1+ICBk[:ZF*7$F^[l$\"1R;))e^I]YF*-

Fc[l6&Fe[lFi[lFf[lFi[l-F$6$7gn7$F($\"1\\NP\")*****\\#F*7$$\"138cmf:3DF

*$\"1#=5JbmAV#F*7$$\"1<E7L>J;DF*$\"1X\\jP5H1CF*7$$\"1ERo**yYCDF*$\"1<D

]sB:(Q#F*7$$\"1N_CmQiKDF*$\"1r6YH\"R:P#F*7$$\"1_yO*zN*[DF*$\"1#GMGD*QY

BF*7$Fa\\l$\"1s#fF')phK#F*7$$\"10dt)fryf#F*$\"1CV9tX=%H#F*7$F/$\"1rU#3

!=,pAF*7$Fi\\l$\"1(*Rc\"yJYB#F*7$F4$\"1R'405hw?#F*7$F9$\"19Wa7$pB;#F*7

$F>$\"1&*4$e7`#H@F*7$FC$\"1RrcApj.@F*7$FH$\"1sxKgDD%3#F*7$FM$\"1dfns`N

n?F*7$FR$\"1(yV7WJC0#F*7$FW$\"1<*pv0Y&R?F*7$Ffn$\"1o,Ij[#z-#F*7$F[o$\"

1@dav&)z=?F*7$F`o$\"1gv^aba4?F*7$Feo$\"1fM\"\\4g6+#F*7$Fjo$\"13V@Euz$*

>F*7$F_p$\"1_r*\\LIw)>F*7$Fdp$\"1\"*y.Hf%3)>F*7$Fip$\"1]IXu1]v>F*7$F^q

$\"1&4ap(4op>F*7$Fcq$\"1>0Nr)Q['>F*7$Fhq$\"1\\p:mS\")f>F*7$F]r$\"1%z`U

%3Fb>F*7$Fbr$\"1mV#=^X2&>F*7$Fgr$\"1&G\\.(\\vY>F*7$F\\s$\"15[F\"*)*fU>

F*7$Fas$\"1Y#\\![#>%Q>F*7$Ffs$\"19pqf*p[$>F*7$F[t$\"1p-R&[36$>F*7$F`t$

\"1KRfRtFF>F*7$Fet$\"1]b?8$fN#>F*7$Fjt$\"1yD$e>n*>>F*7$F_u$\"13qs(Rcf

\">F*7$Fdu$\"1cG<k^I7>F*7$Fiu$\"1Hv3:\\K3>F*7$F^v$\"1Zv.VSh/>F*7$Fcv$

\"1f!e_]./!>F*7$Fhv$\"1HM#[m]i*=F*7$F]w$\"1VM&z?a;*=F*7$Fbw$\"1$3`bwPo

)=F*7$Fgw$\"1D!)objN\")=F*7$F\\x$\"13#>)R(Gb(=F*7$Fax$\"1v^2m\"R)o=F*7

$Ffx$\"1Gpk85Bh=F*7$F[y$\"14^KkP2`=F*7$F`y$\"1S\\W6\"f<%=F*7$Fey$\"1j.

)*)Ga*G=F*7$Fjy$\"1%\\;#H_d5=F*7$F_z$\"1'HKv\"=$))z\"F*7$Fdz$\"1cCYj#*

o$y\"F*7$Fiz$\"11\"ps)H**f<F*7$F^[l$\"1!RVF5h')o\"F*-Fc[l6&Fe[lFf[lFf[

lFi[l-%+AXESLABELSG6$%\"dG%!G-%%VIEWG6$;$\"+++++D!#5$\"+R?\"o[)Fibm%(D

EFAULTG" 1 2 0 1 0 2 9 1 4 2 1.000000 45.000000 45.000000 0 }}}}}

{SECT 0 {PARA 4 "" 0 "" {TEXT -1 27 " The case  of one real root" }}

{SECT 0 {PARA 5 "" 0 "" {TEXT -1 31 "First case: The interval 0..1/4" 

}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 121 "We show that for d in this inte

rval, all roots are < 1/4; we will see that there is always an eigenva

lue > 1/4 elsewhere." }}{PARA 0 "" 0 "" {TEXT -1 309 "Therefore, the r

oots on this interval are irrelevant. There is only one real root; if \+

at a point x the value of the polynomial is positive, than the magnitu

de of the \nreal root is  less than x. We see that the char. polynomia

l is positive at 1/4 for d = 0..1/4, and negative  for d = 1..1/4.  Fo

r any K > 3,  " }{XPPEDIT 18 0 "cos(Pi/K)^2 > 1/4" "6#2*&\"\"\"\"\"\"

\"\"%!\"\"*$-%$cosG6#*&%#PiGF&%\"KGF(\"\"#" }{TEXT -1 69 ", therfore, \+

there is a real eigenvalue of magnitude greater than 1/4." }}{PARA 0 "

> " 0 "" {MPLTEXT 1 0 49 "solve( subs( lambda = 1/4, ButterCharpoly) >

 0 );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$-%*RealRangeG6$,$%)infinityG!

\"\"-%%OpenG6##\"\"\"\"\"%-F$6$-F*6#F-F'" }}}{EXCHG {PARA 0 "" 0 "" 

{TEXT -1 107 "Now build an equation for the square of the magnitude of

 the other two roots; it is a cubic equation again:" }}{PARA 0 "> " 0 

"" {MPLTEXT 1 0 51 "rsq := - se; ssq := expand(te*re); tsq := -te*te; \+

 " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$rsqG,(%\"dG#!#B\"#k#!\"\"F)\"

\"\"*$F&\"\"##\"\"$\"#;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$ssqG,(%

\"dG#\"\"\"\"$c#*$F&\"\"$#!\"\"\"#k*$F&\"\"##F+\"$G\"" }}{PARA 11 "" 

1 "" {XPPMATH 20 "6#>%$tsqG,$*$%\"dG\"\"##!\"\"\"%'4%" }}}{EXCHG 

{PARA 0 "" 0 "" {TEXT -1 74 "Use the same approach: verifying that all

 solutions are < 1/16 on d=1..1/4" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 

56 "solve( subs(x = 1/16, x^3 + rsq*x^2 + ssq*x + tsq) > 0);" }}{PARA 

11 "" 1 "" {XPPMATH 20 "6$-%*RealRangeG6$,$%)infinityG!\"\"-%%OpenG6##

\"\"\"\"\"%-F$6$-F*6##\"\"$F.-F*6#F-" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 

-1 45 "For plots, get the expressions for the roots " }}{PARA 0 "> " 

0 "" {MPLTEXT 1 0 68 "R :=  signum(qe)*sqrt(-pe/3): phi := arccosh( ab

s(qe)/(2*abs(R)^3)):" }}{PARA 11 "" 0 "" {TEXT -1 0 "" }}}{EXCHG 

{PARA 0 "> " 0 "" {MPLTEXT 1 0 134 "r := -2*R*cosh(phi/3)-re/3: c1 := \+

R*( cosh(phi/3) + I*sqrt(3)*sinh(phi/3))-re/3: c2 := R*( cosh(phi/3) +

 I*sqrt(3)*sinh(phi/3)) -re/3:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 

1 0 45 "plot( [ abs(r), abs(c1), abs(c2)], d=0..1/4);" }}{PARA 13 "" 

1 "" {GLPLOT2D 360 288 288 {PLOTDATA 2 "6'-%'CURVESG6$7S7$\"\"!F(7$$\"

1+++T&)G\\a!#=$\"1-#f\"z.yQ_F,7$$\"1+++O&o!>5!#<$\"1)\\!>\"4^!\\%*F,7$

$\"1+++)>)G_:F2$\"1bg]eq]z8F27$$\"1+++&QU!*3#F2$\"1#*)*QRjAw<F27$$\"1+

++uaCBEF2$\"1+j]HfDK@F27$$\"1+++?,_=JF2$\"1GdCZC**HCF27$$\"1+++G$[8j$F

2$\"1I&QZyZ\"3FF27$$\"1+++&*frhTF2$\"1Ckc\"fRm'HF27$$\"1+++lFQ!p%F2$\"

1$zaMd\")z>$F27$$\"1+++?:=M_F2$\"1p/`+lz6MF27$$\"1+++g(fJr&F2$\"1i')p+

nI#e$F27$$\"1*****>\"eP_iF2$\"1Prxp'3ov$F27$$\"1+++Pf!Qz'F2$\"1Nm'\\$

\\!e\"RF27$$\"1+++(=ubJ(F2$\"1gf[#Rxc0%F27$$\"1+++W(*Q*y(F2$\"1RN'e(Ry

sTF27$$\"1+++qA!GN)F2$\"1=#*=A7K,VF27$$\"1,++$e'3I))F2$\"1\\T+E-A-WF27

$$\"1*****Hq\"G&Q*F2$\"1x[^b;a6XF27$$\"1+++eMsw)*F2$\"1`Iu@?&>g%F27$$

\"1+++&H\"fT5!#;$\"1mj#oS;^p%F27$$\"1+++')[$H4\"Fgq$\"1-P)e)4lyZF27$$

\"1+++Ol]Y6Fgq$\"1+l<9w0h[F27$$\"1+++N?q&>\"Fgq$\"1)pr^FPH$\\F27$$\"1+

++Egw[7Fgq$\"17_sw!\\o+&F27$$\"1+++*f%)QI\"Fgq$\"1NW>&*G3!3&F27$$\"1++

+![l=N\"Fgq$\"1P.'[\"H@T^F27$$\"1+++Xho.9Fgq$\"1Uw$*pOy/_F27$$\"1+++i>

Ad9Fgq$\"1f/k`)e!o_F27$$\"1+++;jf4:Fgq$\"1/Qjsk%yK&F27$$\"1+++&>r-c\"F

gq$\"1Au>=h!RQ&F27$$\"1+++4q`;;Fgq$\"1NnW&f,VW&F27$$\"1+++YV4n;Fgq$\"1

&)zsNm2(\\&F27$$\"1+++%4v5s\"Fgq$\"1NN.UT-_bF27$$\"1+++u'*)*p<Fgq$\"1P

9atio+cF27$$\"1+++JiYB=Fgq$\"14Wq>,y_cF27$$\"1+++/Nyt=Fgq$\"13y^&\\U3q

&F27$$\"1+++^&zj#>Fgq$\"1?PQS2>]dF27$$\"1+++-=!y(>Fgq$\"1xHk!)Rk(z&F27

$$\"1+++LhjJ?Fgq$\"1Q0RTwcYeF27$$\"1+++#*\\[$3#Fgq$\"138UF7.$*eF27$$\"

1+++Qz]O@Fgq$\"1d7Yh;&*RfF27$$\"1+++H=4*=#Fgq$\"1MvK$p_f)fF27$$\"1+++i

4TPAFgq$\"1pc-9q!y-'F27$$\"1+++V,z#H#Fgq$\"1;yiLBMvgF27$$\"1+++U>KUBFg

q$\"1c>(*z2^<hF27$$\"1+++qJ8&R#Fgq$\"1T#yrba@;'F27$$\"1+++b-oXCFgq$\"1

<Z4]vh/iF27$$\"+++++D!#5$\"++++]i!#6-%'COLOURG6&%$RGBG$\"#5!\"\"F(F(-F

$6$7S7$F($\"++++]7Fdz7$$\"+T&)G\\a!#7$\"+Bo'[F\"Fdz7$$\"+O&o!>5Fgz$\"+

z#G\")H\"Fdz7$$\"+)>)G_:Fgz$\"+:;(fK\"Fdz7$$\"+&QU!*3#Fgz$\"+K\"4cN\"F

dz7$$\"+uaCBEFgz$\"+$)yY'Q\"Fdz7$$\"+?,_=JFgz$\"+d01;9Fdz7$$\"+G$[8j$F

gz$\"+aSYZ9Fdz7$$\"+&*frhTFgz$\"+,&=0[\"Fdz7$$\"+lFQ!p%Fgz$\"+dn#Q^\"F

dz7$$\"+?:=M_Fgz$\"+biD[:Fdz7$$\"+g(fJr&Fgz$\"+&z!ey:Fdz7$$\"+7eP_iFgz

$\"+rke7;Fdz7$$\"+Pf!Qz'Fgz$\"+u%ykk\"Fdz7$$\"+(=ubJ(Fgz$\"+lP\")y;Fdz

7$$\"+W(*Q*y(Fgz$\"+&GYyq\"Fdz7$$\"+qA!GN)Fgz$\"+Xy!>u\"Fdz7$$\"+$e'3I

))Fgz$\"+8(R.x\"Fdz7$$\"+.<G&Q*Fgz$\"+5\")*G!=Fdz7$$\"+eMsw)*Fgz$\"+O1

CJ=Fdz7$$\"+&H\"fT5Fdz$\"+91\"='=Fdz7$$\"+')[$H4\"Fdz$\"+]MS!*=Fdz7$$

\"+Ol]Y6Fdz$\"+Gzp>>Fdz7$$\"+N?q&>\"Fdz$\"+**e6Y>Fdz7$$\"+Egw[7Fdz$\"+

Wh4u>Fdz7$$\"+*f%)QI\"Fdz$\"+0**f-?Fdz7$$\"+![l=N\"Fdz$\"+,V&p-#Fdz7$$

\"+Xho.9Fdz$\"+0gy_?Fdz7$$\"+i>Ad9Fdz$\"+=o'*y?Fdz7$$\"+;jf4:Fdz$\"+x7

4/@Fdz7$$\"+&>r-c\"Fdz$\"+6&\\z7#Fdz7$$\"+4q`;;Fdz$\"+A3$R:#Fdz7$$\"+Y

V4n;Fdz$\"+e%Go<#Fdz7$$\"+%4v5s\"Fdz$\"+7'=3?#Fdz7$$\"+u'*)*p<Fdz$\"+(

3d@A#Fdz7$$\"+JiYB=Fdz$\"+k$f]C#Fdz7$$\"+/Nyt=Fdz$\"+S-@mAFdz7$$\"+^&z

j#>Fdz$\"+TY\"zG#Fdz7$$\"+-=!y(>Fdz$\"+\"=V(3BFdz7$$\"+LhjJ?Fdz$\"+PD9

IBFdz7$$\"+#*\\[$3#Fdz$\"+2yO]BFdz7$$\"+Qz]O@Fdz$\"+7%o1P#Fdz7$$\"+H=4

*=#Fdz$\"+DjU!R#Fdz7$$\"+i4TPAFdz$\"+x\"f#3CFdz7$$\"+V,z#H#Fdz$\"+w[KG

CFdz7$$\"+U>KUBFdz$\"+i2%fW#Fdz7$$\"+qJ8&R#Fdz$\"+v\\QkCFdz7$$\"+b-oXC

Fdz$\"+,vr\"[#Fdz7$FbzFbz-Fiz6&F[[lF(F\\[lF(-F$6$Fa[l-Fiz6&F[[lF\\[lF

\\[lF(-%+AXESLABELSG6$%\"dG%!G-%%VIEWG6$;F(Fbz%(DEFAULTG" 1 2 0 1 0 2 

9 1 4 2 1.000000 45.000000 45.000000 0 }}}}}{SECT 0 {PARA 5 "" 0 "" 

{TEXT -1 34 "Second case: interval DiscrRoot..1" }}{EXCHG {PARA 0 "" 

0 "" {TEXT -1 374 "In this case, we show that the real root is the lar

gest;  we have already observed that  on 3/4 ..1 the magnitude of the \+

complex roots (when there are \ncomplex roots)  is < 1/4; hence, it is

 sufficien to show that the real root is greater than 1/4. But we have

 seen already, that the characteristic polynomial is negative at 1/4 f

or d > 1/4. Therefore, the real root > 1/4. " }}{PARA 0 "" 0 "" {TEXT 

-1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 98 "R :=  sqrt(-pe/3)

: phi := arccosh( abs(qe)/(2*abs(R)^3)): AbsDominantEV2 := 2*R*cosh(ph

i/3)-re/3; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%/AbsDominantEV2G,**&,

,\"\"\"F(*$%\"dG\"\"$!$#>*$F*\"\"#\"$[\"F*!#@*$F*\"\"%\"#k#F(F.-%%cosh

G6#,$-%(arccoshG6#,$*&-%$absG6#,0F*#F(\"$o(F-#\"#b\"%_6F1#\"#t\"$W\"F)

#!#>F3*$F*\"\"'#F.\"#F*$F*\"\"&#!\"\"F+#F(\"%7pF(F(-F?6#F'#!\"$F.FU#F(

F+F(#F(\"#7FenF(F-FRF*F4" }}}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 17 "Plo

t of all roots" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 168 "display(p

lot( [abs(r),abs(c1)], d = 0..1/4,  color=black), plot([r1,r2,r3],d=1/

4..DiscrRoot,  color=black), plot([abs(r),abs(c1)],d=DiscrRoot..1.0000

01,  color=black));" }}{PARA 13 "" 1 "" {GLPLOT2D 468 432 432 

{PLOTDATA 2 "6+-%'CURVESG6$7S7$\"\"!F(7$$\"1+++T&)G\\a!#=$\"1-#f\"z.yQ

_F,7$$\"1+++O&o!>5!#<$\"1)\\!>\"4^!\\%*F,7$$\"1+++)>)G_:F2$\"1bg]eq]z8

F27$$\"1+++&QU!*3#F2$\"1#*)*QRjAw<F27$$\"1+++uaCBEF2$\"1+j]HfDK@F27$$

\"1+++?,_=JF2$\"1GdCZC**HCF27$$\"1+++G$[8j$F2$\"1I&QZyZ\"3FF27$$\"1+++

&*frhTF2$\"1Ckc\"fRm'HF27$$\"1+++lFQ!p%F2$\"1$zaMd\")z>$F27$$\"1+++?:=

M_F2$\"1p/`+lz6MF27$$\"1+++g(fJr&F2$\"1i')p+nI#e$F27$$\"1*****>\"eP_iF

2$\"1Prxp'3ov$F27$$\"1+++Pf!Qz'F2$\"1Nm'\\$\\!e\"RF27$$\"1+++(=ubJ(F2$

\"1gf[#Rxc0%F27$$\"1+++W(*Q*y(F2$\"1RN'e(RysTF27$$\"1+++qA!GN)F2$\"1=#

*=A7K,VF27$$\"1,++$e'3I))F2$\"1\\T+E-A-WF27$$\"1*****Hq\"G&Q*F2$\"1x[^

b;a6XF27$$\"1+++eMsw)*F2$\"1`Iu@?&>g%F27$$\"1+++&H\"fT5!#;$\"1mj#oS;^p

%F27$$\"1+++')[$H4\"Fgq$\"1-P)e)4lyZF27$$\"1+++Ol]Y6Fgq$\"1+l<9w0h[F27

$$\"1+++N?q&>\"Fgq$\"1)pr^FPH$\\F27$$\"1+++Egw[7Fgq$\"17_sw!\\o+&F27$$

\"1+++*f%)QI\"Fgq$\"1NW>&*G3!3&F27$$\"1+++![l=N\"Fgq$\"1P.'[\"H@T^F27$

$\"1+++Xho.9Fgq$\"1Uw$*pOy/_F27$$\"1+++i>Ad9Fgq$\"1f/k`)e!o_F27$$\"1++

+;jf4:Fgq$\"1/Qjsk%yK&F27$$\"1+++&>r-c\"Fgq$\"1Au>=h!RQ&F27$$\"1+++4q`

;;Fgq$\"1NnW&f,VW&F27$$\"1+++YV4n;Fgq$\"1&)zsNm2(\\&F27$$\"1+++%4v5s\"

Fgq$\"1NN.UT-_bF27$$\"1+++u'*)*p<Fgq$\"1P9atio+cF27$$\"1+++JiYB=Fgq$\"

14Wq>,y_cF27$$\"1+++/Nyt=Fgq$\"13y^&\\U3q&F27$$\"1+++^&zj#>Fgq$\"1?PQS

2>]dF27$$\"1+++-=!y(>Fgq$\"1xHk!)Rk(z&F27$$\"1+++LhjJ?Fgq$\"1Q0RTwcYeF

27$$\"1+++#*\\[$3#Fgq$\"138UF7.$*eF27$$\"1+++Qz]O@Fgq$\"1d7Yh;&*RfF27$

$\"1+++H=4*=#Fgq$\"1MvK$p_f)fF27$$\"1+++i4TPAFgq$\"1pc-9q!y-'F27$$\"1+

++V,z#H#Fgq$\"1;yiLBMvgF27$$\"1+++U>KUBFgq$\"1c>(*z2^<hF27$$\"1+++qJ8&

R#Fgq$\"1T#yrba@;'F27$$\"1+++b-oXCFgq$\"1<Z4]vh/iF27$$\"+++++D!#5$\"++

++]i!#6-%'COLOURG6&%$RGBGF(F(F(-F$6$7S7$F($\"++++]7Fdz7$$\"+T&)G\\a!#7

$\"+Bo'[F\"Fdz7$$\"+O&o!>5Fgz$\"+z#G\")H\"Fdz7$$\"+)>)G_:Fgz$\"+:;(fK

\"Fdz7$$\"+&QU!*3#Fgz$\"+K\"4cN\"Fdz7$$\"+uaCBEFgz$\"+$)yY'Q\"Fdz7$$\"

+?,_=JFgz$\"+d01;9Fdz7$$\"+G$[8j$Fgz$\"+aSYZ9Fdz7$$\"+&*frhTFgz$\"+,&=

0[\"Fdz7$$\"+lFQ!p%Fgz$\"+dn#Q^\"Fdz7$$\"+?:=M_Fgz$\"+biD[:Fdz7$$\"+g(

fJr&Fgz$\"+&z!ey:Fdz7$$\"+7eP_iFgz$\"+rke7;Fdz7$$\"+Pf!Qz'Fgz$\"+u%ykk

\"Fdz7$$\"+(=ubJ(Fgz$\"+lP\")y;Fdz7$$\"+W(*Q*y(Fgz$\"+&GYyq\"Fdz7$$\"+

qA!GN)Fgz$\"+Xy!>u\"Fdz7$$\"+$e'3I))Fgz$\"+8(R.x\"Fdz7$$\"+.<G&Q*Fgz$

\"+5\")*G!=Fdz7$$\"+eMsw)*Fgz$\"+O1CJ=Fdz7$$\"+&H\"fT5Fdz$\"+91\"='=Fd

z7$$\"+')[$H4\"Fdz$\"+]MS!*=Fdz7$$\"+Ol]Y6Fdz$\"+Gzp>>Fdz7$$\"+N?q&>\"

Fdz$\"+**e6Y>Fdz7$$\"+Egw[7Fdz$\"+Wh4u>Fdz7$$\"+*f%)QI\"Fdz$\"+0**f-?F

dz7$$\"+![l=N\"Fdz$\"+,V&p-#Fdz7$$\"+Xho.9Fdz$\"+0gy_?Fdz7$$\"+i>Ad9Fd

z$\"+=o'*y?Fdz7$$\"+;jf4:Fdz$\"+x74/@Fdz7$$\"+&>r-c\"Fdz$\"+6&\\z7#Fdz

7$$\"+4q`;;Fdz$\"+A3$R:#Fdz7$$\"+YV4n;Fdz$\"+e%Go<#Fdz7$$\"+%4v5s\"Fdz

$\"+7'=3?#Fdz7$$\"+u'*)*p<Fdz$\"+(3d@A#Fdz7$$\"+JiYB=Fdz$\"+k$f]C#Fdz7

$$\"+/Nyt=Fdz$\"+S-@mAFdz7$$\"+^&zj#>Fdz$\"+TY\"zG#Fdz7$$\"+-=!y(>Fdz$

\"+\"=V(3BFdz7$$\"+LhjJ?Fdz$\"+PD9IBFdz7$$\"+#*\\[$3#Fdz$\"+2yO]BFdz7$

$\"+Qz]O@Fdz$\"+7%o1P#Fdz7$$\"+H=4*=#Fdz$\"+DjU!R#Fdz7$$\"+i4TPAFdz$\"

+x\"f#3CFdz7$$\"+V,z#H#Fdz$\"+w[KGCFdz7$$\"+U>KUBFdz$\"+i2%fW#Fdz7$$\"

+qJ8&R#Fdz$\"+v\\QkCFdz7$$\"+b-oXCFdz$\"+,vr\"[#Fdz7$FbzFbzFhz-F$6$7U7

$$\"1+++++++DFgq$\"1.+++++]iF27$$\"1R4)\\Y&\\IEFgq$\"14m[ML?ejF27$$\"1

%R08()QSu#Fgq$\"1nX/Ubr^kF27$$\"1/9&oII<(GFgq$\"1!['>FDbclF27$$\"1^(>T

;o-+$Fgq$\"1uE3<t3imF27$$\"1S)*Q.^>GJFgq$\"14;.]\"[uw'F27$$\"1*H\")=v*

zYKFgq$\"1-^H2xnloF27$$\"1^[a&*zgpLFgq$\"11_5Aa<opF27$$\"102#oX;m\\$Fg

q$\"1fv&e*3DvqF27$$\"1v/N+w@BOFgq$\"10Opo=H$=(F27$$\"1`%HxVUMv$Fgq$\"1

Nv!f6:gH(F27$$\"1:dPXX9oQFgq$\"1sbIQ[\"oR(F27$$\"1(4l9&>F(*RFgq$\"1(3I

'yF=7vF27$$\"1(=!4n&Hp7%Fgq$\"1cXfHcCIwF27$$\"11pr/(y=D%Fgq$\"1p*4q-Fj

u(F27$$\"1vK-#\\W`O%Fgq$\"1L_Ud`'Q&yF27$$\"1ikx(Gm-]%Fgq$\"1FqZ')>e%)z

F27$$\"1&\\+luiXh%Fgq$\"1ze?(p5z4)F27$$\"12qe*p;vu%Fgq$\"1zu#Q$p&HB)F2

7$$\"1[*[iZ._'[Fgq$\"1l7[OGeb$)F27$$\"1#z(fAXK%*\\Fgq$\"1s:BCJp$\\)F27

$$\"1([*=$Hys6&Fgq$\"1'3I>r8*G')F27$$\"1xV5awcX_Fgq$\"17#G*)QBTx)F27$$

\"1q%G]LxLO&Fgq$\"1MM,'zD9\"*)F27$$\"1u,W\"*4X!\\&Fgq$\"1pn<;s0k!*F27$

$\"1G902[WAcFgq$\"1*H\\i#H#zA*F27$$\"1b1c6eMPdFgq$\"1$\\a<+#Hv$*F27$$

\"1*\\YU/U9'eFgq$\"1=vke#Q(R&*F27$$\"1#3OafX'*)fFgq$\"1!=b#Gqz:(*F27$$

\"1=bcex1:hFgq$\"1U1t+gb%*)*F27$$\"1=2[],UOiFgq$\"1$[a;#>T25Fgq7$$\"1B

ho\"Hh6P'Fgq$\"1BM')\\8<G5Fgq7$$\"1JN\"**>KA\\'Fgq$\"1j'>-&HiZ5Fgq7$$

\"1AU^O7]@mFgq$\"1V/$[s)Hp5Fgq7$$\"1E5$o>Q'QnFgq$\"1tjWq'>)*3\"Fgq7$$

\"1$)HQM)*pmoFgq$\"17)y@p+L6\"Fgq7$$\"1*eU_&e>()pFgq$\"1+tQo')[O6Fgq7$

$\"1>6R;*[J6(Fgq$\"1/>mC-)>;\"Fgq7$$\"1etyb5HOsFgq$\"1B!=uxz#)=\"Fgq7$

$\"16d^j%4_O(Fgq$\"1Ez$\\p_u@\"Fgq7$$\"1EVZ7KP*[(Fgq$\"1L[()*z]tC\"Fgq

7$$\"1H@:z&[jh(Fgq$\"1x#=s\\M+G\"Fgq7$$\"1g`oDDFUxFgq$\"1Y)>_G?\\J\"Fg

q7$$\"1JUfaN)z&yFgq$\"1[\"e>6z&\\8Fgq7$$\"16nq^9g!*zFgq$\"1;t\"3JEJR\"

Fgq7$$\"1UN$)zk@4\")Fgq$\"1;*3(H\\hO9Fgq7$$\"1XShR[oN#)Fgq$\"14SZkc&)*

[\"Fgq7$$\"1l&o#=!3iH)Fgq$\"1(pV:!49>:Fgq7$$\"1%3Bp>JnN)Fgq$\"1=k\"*ya

U_:Fgq7$$\"1U:'zhr<U)Fgq$\"1AW4O*Gjf\"Fgq7$$\"1+++R?\"o[)Fgq$\"1PMMQRl

)o\"FgqFhz-F$6$7U7$Fcjl$\"1^ki=+++DFgq7$$\"1q/\\KxClDFgq$\"1o8$)z%HKt#

Fgq7$Fhjl$\"1[*pSUg*[GFgq7$$\"1nJ9orE(o#Fgq$\"1$poeDFO$HFgq7$F][m$\"1(

\\?&>2D5IFgq7$Fb[m$\"1eT[*R()[;$Fgq7$Fg[m$\"19t(H[zZI$Fgq7$F\\\\m$\"1V

s-d/NLMFgq7$Fa\\m$\"1>I)QV3_a$Fgq7$Ff\\m$\"1>o1uK\"[l$Fgq7$F[]m$\"1x0z

*[NBw$Fgq7$F`]m$\"1*[P\"y0=kQFgq7$Fe]m$\"1;%o$oU!Q'RFgq7$Fj]m$\"1/`HOD

[ZSFgq7$F_^m$\"1=,U*yDt8%Fgq7$Fd^m$\"1Y+fF\\0BUFgq7$Fi^m$\"1Vv>w1a,VFg

q7$F^_m$\"1V9*Qhw$pVFgq7$Fc_m$\"1l$*)yjbeW%Fgq7$Fh_m$\"1'3Q9WLr]%Fgq7$

F]`m$\"1<zv(*oSuXFgq7$Fb`m$\"1#HWGd(QIYFgq7$Fg`m$\"1:Whhc(zo%Fgq7$F\\a

m$\"1(fU8^,\"RZFgq7$Faam$\"1p21Hcf)y%Fgq7$Ffam$\"1nB!)3oeI[Fgq7$F[bm$

\"1OrKlc;s[Fgq7$F`bm$\"14!p!4rE6\\Fgq7$Febm$\"1g`Jhe!>%\\Fgq7$Fjbm$\"1

q'38ZI9(\\Fgq7$F_cm$\"1))>%[\"f-)*\\Fgq7$Fdcm$\"17\\Qb8=?]Fgq7$Ficm$\"

1A=!*yu&z.&Fgq7$F^dm$\"1&zq%pXW`]Fgq7$Fcdm$\"1o$=<H7N1&Fgq7$Fhdm$\"1Cu

L_.?q]Fgq7$F]em$\"15O)p5*fs]Fgq7$Fbem$\"1vge#*))=r]Fgq7$Fgem$\"1K7qdQ'

f1&Fgq7$F\\fm$\"1<dH\">+k0&Fgq7$Fafm$\"1?JI;#GH/&Fgq7$Fffm$\"1x9]+TPC]

Fgq7$F[gm$\"1[YWn\"4@+&Fgq7$F`gm$\"1w%>vjsZ(\\Fgq7$Fegm$\"1GIY.\"zH%\\

Fgq7$Fjgm$\"1`2=,>`4\\Fgq7$F_hm$\"1rgH*fXg'[Fgq7$Fdhm$\"1W1Q4jJA[Fgq7$

Fihm$\"1.d)z)eWqZFgq7$Fcim$\"1+ICBk[:ZFgq7$F]jm$\"1R;))e^I]YFgqFhz-F$6

$7gn7$Fcjl$\"1\\NP\")*****\\#Fgq7$$\"138cmf:3DFgq$\"1#=5JbmAV#Fgq7$$\"

1<E7L>J;DFgq$\"1X\\jP5H1CFgq7$$\"1ERo**yYCDFgq$\"1<D]sB:(Q#Fgq7$$\"1N_

CmQiKDFgq$\"1r6YH\"R:P#Fgq7$$\"1_yO*zN*[DFgq$\"1#GMGD*QYBFgq7$Fhjm$\"1

s#fF')phK#Fgq7$$\"10dt)fryf#Fgq$\"1CV9tX=%H#Fgq7$Fhjl$\"1rU#3!=,pAFgq7

$F`[n$\"1(*Rc\"yJYB#Fgq7$F][m$\"1R'405hw?#Fgq7$Fb[m$\"19Wa7$pB;#Fgq7$F

g[m$\"1&*4$e7`#H@Fgq7$F\\\\m$\"1RrcApj.@Fgq7$Fa\\m$\"1sxKgDD%3#Fgq7$Ff

\\m$\"1dfns`Nn?Fgq7$F[]m$\"1(yV7WJC0#Fgq7$F`]m$\"1<*pv0Y&R?Fgq7$Fe]m$

\"1o,Ij[#z-#Fgq7$Fj]m$\"1@dav&)z=?Fgq7$F_^m$\"1gv^aba4?Fgq7$Fd^m$\"1fM

\"\\4g6+#Fgq7$Fi^m$\"13V@Euz$*>Fgq7$F^_m$\"1_r*\\LIw)>Fgq7$Fc_m$\"1\"*

y.Hf%3)>Fgq7$Fh_m$\"1]IXu1]v>Fgq7$F]`m$\"1&4ap(4op>Fgq7$Fb`m$\"1>0Nr)Q

['>Fgq7$Fg`m$\"1\\p:mS\")f>Fgq7$F\\am$\"1%z`U%3Fb>Fgq7$Faam$\"1mV#=^X2

&>Fgq7$Ffam$\"1&G\\.(\\vY>Fgq7$F[bm$\"15[F\"*)*fU>Fgq7$F`bm$\"1Y#\\![#

>%Q>Fgq7$Febm$\"19pqf*p[$>Fgq7$Fjbm$\"1p-R&[36$>Fgq7$F_cm$\"1KRfRtFF>F

gq7$Fdcm$\"1]b?8$fN#>Fgq7$Ficm$\"1yD$e>n*>>Fgq7$F^dm$\"13qs(Rcf\">Fgq7

$Fcdm$\"1cG<k^I7>Fgq7$Fhdm$\"1Hv3:\\K3>Fgq7$F]em$\"1Zv.VSh/>Fgq7$Fbem$

\"1f!e_]./!>Fgq7$Fgem$\"1HM#[m]i*=Fgq7$F\\fm$\"1VM&z?a;*=Fgq7$Fafm$\"1

$3`bwPo)=Fgq7$Fffm$\"1D!)objN\")=Fgq7$F[gm$\"13#>)R(Gb(=Fgq7$F`gm$\"1v

^2m\"R)o=Fgq7$Fegm$\"1Gpk85Bh=Fgq7$Fjgm$\"14^KkP2`=Fgq7$F_hm$\"1S\\W6

\"f<%=Fgq7$Fdhm$\"1j.)*)Ga*G=Fgq7$Fihm$\"1%\\;#H_d5=Fgq7$F^im$\"1'HKv

\"=$))z\"Fgq7$Fcim$\"1cCYj#*o$y\"Fgq7$Fhim$\"11\"ps)H**f<Fgq7$F]jm$\"1

!RVF5h')o\"FgqFhz-F$6$7Y7$$\"+R?\"o[)Fdz$\"+n^I]YFdz7$$\"1+++[az>&)Fgq

$\"1ypMQEsKYFgq7$$\"1+++OT\\[&)Fgq$\"1eFKL\\1<YFgq7$$\"1+++7)o2e)Fgq$

\"1lW5g'\\!*f%Fgq7$$\"1,++EuD8')Fgq$\"1M6k<AZ!e%Fgq7$$\"1+++F;fX')Fgq$

\"1%p\\?<L:c%Fgq7$$\"1+++r&pbn)Fgq$\"1<;:I^cVXFgq7$$\"1+++%**4mq)Fgq$

\"1ylk'yOX_%Fgq7$$\"1+++X?rQ()Fgq$\"1tP#Ri%R/XFgq7$$\"1+++X6rq()Fgq$\"

1'\\W]rPQ[%Fgq7$$\"1+++^hi.))Fgq$\"14!*o_3=iWFgq7$$\"1+++2xhK))Fgq$\"1

T5'e9lEW%Fgq7$$\"1+++K`Dl))Fgq$\"1Nb!ew)=?WFgq7$$\"1+++rp-)*))Fgq$\"1p

0Sve1(R%Fgq7$$\"1*****p^3'H*)Fgq$\"1!*34.>CuVFgq7$$\"1+++'e(Ge*)Fgq$\"

1\\bGkA/`VFgq7$$\"1+++u(*Q#**)Fgq$\"1Gt@4$HsK%Fgq7$$\"1++++)y7-*Fgq$\"

1J*o(*HK[I%Fgq7$$\"1+++/O)[0*Fgq$\"1Sei$>Y\"yUFgq7$$\"1+++^&HY3*Fgq$\"

1$)GgYl$RD%Fgq7$$\"1+++pbE<\"*Fgq$\"1_#=JC:nA%Fgq7$$\"1+++vFM[\"*Fgq$

\"1C7p(eF,?%Fgq7$$\"1,++!eo2=*Fgq$\"1^RX;NmrTFgq7$$\"1+++\"fX0@*Fgq$\"

18BQ@j%[9%Fgq7$$\"1+++@TmU#*Fgq$\"1))3H4&e^6%Fgq7$$\"1+++Yi-w#*Fgq$\"1

'pDRSUM3%Fgq7$$\"1+++u!o]I*Fgq$\"1f4u6j1bSFgq7$$\"1+++WSVO$*Fgq$\"12OX

LKdBSFgq7$$\"1+++g\"Q)o$*Fgq$\"1wXd]:1!*RFgq7$$\"1+++m#R0S*Fgq$\"1x255

eDcRFgq7$$\"1+++;<@J%*Fgq$\"1<Jzg4_ARFgq7$$\"1+++U#o_Y*Fgq$\"1y#f%GZz$

)QFgq7$$\"1+++X&pe\\*Fgq$\"1s+V])ox%QFgq7$$\"1+++oHaG&*Fgq$\"1FU\"Rz3z

!QFgq7$$\"1+++Y*\\\"e&*Fgq$\"1#*RI$pM/x$Fgq7$$\"1+++#>=0f*Fgq$\"1f0r\\

c%ys$Fgq7$$\"1+++!>u4i*Fgq$\"1)4z)3X1'o$Fgq7$$\"1+++$[4Gl*Fgq$\"1F\"Hq

T5/k$Fgq7$$\"1+++,V$Ro*Fgq$\"18wZ+Pc$f$Fgq7$$\"1++++\">lr*Fgq$\"1uE-[%

G=a$Fgq7$$\"1*****\\8-zu*Fgq$\"1sF#>'Q'*)[$Fgq7$$\"1+++@e**z(*Fgq$\"1a

/3bGAJMFgq7$$\"1+++cP#=\")*Fgq$\"1#*zRF9YpLFgq7$$\"1+++A.2T)*Fgq$\"1$*

f7K^t2LFgq7$$\"1+++(=!fu)*Fgq$\"1LH@y)=#HKFgq7$$\"1+++`2d/**Fgq$\"1`W*

z#Q2\\JFgq7$$\"1+++\"HOl$**Fgq$\"1x>k-:<ZIFgq7$$\"1+++TQ$=&**Fgq$\"1fu

sP-\\))HFgq7$$\"1+++*QJr'**Fgq$\"1d_WdA_=HFgq7$$\"1+++V5Nv**Fgq$\"1%pj

=SEK(GFgq7$$\"1+++&pqN)**Fgq$\"1QX#z!HQ=GFgq7$$\"1+++A0o()**Fgq$\"10d=

V*)*[y#Fgq7$$\"1+++[.z\"***Fgq$\"1Zl0f'3Tu#Fgq7$$\"1+++u,!f***Fgq$\"1;

Y%o*eO)o#Fgq7$$\"(,++\"!\"'$\"+1Z5+DFdzFhz-F$6$7Y7$Fe`o$\"+Cvl)o\"Fdz7

$$\"+[az>&)Fdz$\"+;M9&p\"Fdz7$$\"+OT\\[&)Fdz$\"+)ys3q\"Fdz7$$\"+7)o2e)

Fdz$\"+#*[T2<Fdz7$$\"+EuD8')Fdz$\"+\\'4Tr\"Fdz7$$\"+F;fX')Fdz$\"+9a)3s

\"Fdz7$$\"+r&pbn)Fdz$\"+7;FF<Fdz7$$\"+%**4mq)Fdz$\"+JO*Rt\"Fdz7$$\"+X?

rQ()Fdz$\"+/r1T<Fdz7$$\"+X6rq()Fdz$\"+>dC[<Fdz7$$\"+^hi.))Fdz$\"+(Qodv

\"Fdz7$$\"+2xhK))Fdz$\"+![:Dw\"Fdz7$$\"+K`Dl))Fdz$\"+`DDq<Fdz7$$\"+rp-

)*))Fdz$\"+F'y\"y<Fdz7$$\"+<&3'H*)Fdz$\"+OF(fy\"Fdz7$$\"+'e(Ge*)Fdz$\"

+7!*=$z\"Fdz7$$\"+u(*Q#**)Fdz$\"+@&\\>!=Fdz7$$\"++)y7-*Fdz$\"+e1`4=Fdz

7$$\"+/O)[0*Fdz$\"+pKa==Fdz7$$\"+^&HY3*Fdz$\"+gPqE=Fdz7$$\"+pbE<\"*Fdz

$\"+D`'e$=Fdz7$$\"+vFM[\"*Fdz$\"+eH![%=Fdz7$$\"+!eo2=*Fdz$\"+@OOa=Fdz7

$$\"+\"fX0@*Fdz$\"+?tOj=Fdz7$$\"+@TmU#*Fdz$\"+DWLt=Fdz7$$\"+Yi-w#*Fdz$

\"+xk)R)=Fdz7$$\"+u!o]I*Fdz$\"+tR_$*=Fdz7$$\"+WSVO$*Fdz$\"+T67/>Fdz7$$

\"+g\"Q)o$*Fdz$\"+!)eT:>Fdz7$$\"+m#R0S*Fdz$\"+4O$o#>Fdz7$$\"+;<@J%*Fdz

$\"+MfDQ>Fdz7$$\"+U#o_Y*Fdz$\"+q\"49&>Fdz7$$\"+X&pe\\*Fdz$\"+\\)*oj>Fd

z7$$\"+oHaG&*Fdz$\"+>QLx>Fdz7$$\"+Y*\\\"e&*Fdz$\"+C1A!*>Fdz7$$\"+#>=0f

*Fdz$\"+vK%\\+#Fdz7$$\"+!>u4i*Fdz$\"+'4t%>?Fdz7$$\"+$[4Gl*Fdz$\"+HfXN?

Fdz7$$\"+,V$Ro*Fdz$\"+<1)>0#Fdz7$$\"++\">lr*Fdz$\"+YtQq?Fdz7$$\"+N@!zu

*Fdz$\"+O'z$*3#Fdz7$$\"+@e**z(*Fdz$\"+Q>N5@Fdz7$$\"+cP#=\")*Fdz$\"+%pn

I8#Fdz7$$\"+A.2T)*Fdz$\"+7Z3c@Fdz7$$\"+(=!fu)*Fdz$\"+-B&e=#Fdz7$$\"+`2

d/**Fdz$\"+z0&o@#Fdz7$$\"+\"HOl$**Fdz$\"+hpCdAFdz7$$\"+TQ$=&**Fdz$\"+S

W0\"G#Fdz7$$\"+*QJr'**Fdz$\"+r'3+J#Fdz7$$\"+V5Nv**Fdz$\"+@c5HBFdz7$$\"

+&pqN)**Fdz$\"+Gki_BFdz7$$\"+A0o()**Fdz$\"+1[@nBFdz7$$\"+[.z\"***Fdz$

\"+%)RB&Q#Fdz7$$\"+u,!f***Fdz$\"+[7L5CFdz7$Fcap$\"+g![1[#FdzFhz-%+AXES

LABELSG6$%\"dG%!G-%%VIEWG6$;F(Fcap%(DEFAULTG" 1 2 0 1 0 2 9 1 4 2 

1.000000 45.000000 45.000000 0 }}}}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 

61 " The magnitude of the subdominant eigenvalue  decreases for  " }

{XPPEDIT 18 0 "d" "6#%\"dG" }{TEXT -1 37 "  from approximately 0.67600

423  to 1" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 190 "To show that the sub

dominant eigenvalues of the Butterfly scheme are not in the correct bl

ock for sufficiently large valences, we show that the largest eigenval

ue decreases as a function of " }{XPPEDIT 18 0 "d" "6#%\"dG" }{TEXT 

-1 195 " near 1.  To do this, we find the sign of the derivative; it i

s suficient to evaluate the derivative at a single point, and to show \+

that the derivative is not zero anywhere on  an interval.  Let " }

{XPPEDIT 18 0 "y(d)" "6#-%\"yG6#%\"dG" }{TEXT -1 32 "  be the root as \+

a function of  " }{XPPEDIT 18 0 "d" "6#%\"dG" }{TEXT -1 38 ". Then  di

fferentiating the  equation " }{XPPEDIT 18 0 "y^3 + r(d)*y^2 +  s(d)*y

 + t(d) = 0" "6#/,**$%\"yG\"\"$\"\"\"*&-%\"rG6#%\"dGF(*$F&\"\"#F(F(*&-

%\"sG6#F-F(F&F(F(-%\"tG6#F-F(\"\"!" }{TEXT -1 16 " , and setting  " }

{XPPEDIT 18 0 "diff(y,d)" "6#-%%diffG6$%\"yG%\"dG" }{TEXT -1 38 " to z

ero, we observe that at a point  " }{XPPEDIT 18 0 "d[0]" "6#&%\"dG6#\"

\"!" }{TEXT -1 42 " where the derivative is zero, the value  " }

{XPPEDIT 18 0 "y(d[0])" "6#-%\"yG6#&%\"dG6#\"\"!" }{TEXT -1 26 "  sati

sfies the equation  " }{XPPEDIT 18 0 "diff(r,d) *y^2 + diff(s,d)*y + d

iff(t,d) = 0" "6#/,(*&-%%diffG6$%\"rG%\"dG\"\"\"*$%\"yG\"\"#F+F+*&-F'6

$%\"sGF*F+F-F+F+-F'6$%\"tGF*F+\"\"!" }{TEXT -1 39 ".   It is sufficien

t to show that  for " }{XPPEDIT 18 0 "d" "6#%\"dG" }{TEXT -1 132 " on \+

a given interval that the largest root of the orginal equation is not \+

the root of the equation with differentiated coefficients." }}{PARA 0 

"> " 0 "" {MPLTEXT 1 0 59 "diffCharpoly := diff(re,d)*y^2 + diff(se,d)

*y + diff(te,d);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%-diffCharpolyG,(

*&,&%\"dG\"\"##!\"$F)\"\"\"F,%\"yGF)F,*&,&#\"#B\"#kF,F(#F+\"\")F,F-F,F

,#!\"\"F2F," }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 89 "This is just a qua

dratic equation and we can immediately determine when it has no roots:

 " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 89 "solve( coeff(diffCharpoly, y)^

2 - 4*rem(diffCharpoly,y,y)*coeff(diffCharpoly,y^2) < 0,d);" }}{PARA 

11 "" 1 "" {XPPMATH 20 "6#-%*RealRangeG6$-%%OpenG6##\"#H\"#s-F'6##\"\"

&\"\")" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 34 " We consider the interv

al 5/8..1; " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 283 "On this interval \+

there is in fact a point where the magnitude of the largest root of th

e characteristic polynomial is maximal. It is useful to find it more p

recisely. We use Groebner bases package to eliminate y from the system

 of two equations and find a polynomial equation for d; " }{MPLTEXT 0 

21 8 "finduni " }{TEXT -1 86 "finds the minimal univariate polynomial \+

in the ideal generated by the two polynomials:" }}{PARA 0 "> " 0 "" 

{MPLTEXT 1 0 77 "dEquation := finduni( d, [subs( lambda = y, ButterCha

rpoly), diffCharpoly]); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*dEquati

onG,.\"\"*\"\"\"%\"dG!#[*$F(\"\"#\"$K$*$F(\"\"$!$g**$F(\"\"%\"%_6*$F(

\"\"&!$7&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 36 "Now find a rational \+

interval for d; " }{MPLTEXT 0 21 9 "realroot " }{TEXT -1 93 "provides \+

us with guaranteed bounds on all real roots.  Luckily, there is a sing

le real root: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "IntervalDominantM

ax := op(realroot( dEquation, 1/10^7)); " }}{PARA 11 "" 1 "" {XPPMATH 

20 "6#>%4IntervalDominantMaxG7$#\")p9M6\");sx;#\"(N2n&\"(3')Q)" }}}

{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "map(evalf, IntervalDominantM

ax);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$$\"5LOZ5w4B/gn!#?$\"5s6&\\2e

!H/gnF&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 315 "Evaluating the deriva

tive at  a point, we get a negative value; we conclude that the deriva

tive is negative  for d  greater than the value above.\nWe use the alg

ebraic value of the root returned by solve, rather than transcedental \+

equation, because interval  inapply does not work properly for  hyperb

olic functions." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 99 "IntervDeriv := i

napply( diff(op(1, [solve( ButterCharpoly, lambda)]),d),d): eval(Inter

vDeriv(0.9));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$$!5YZ3gFbH@7x!#?$!5

om!*fFbH@7xF&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 103 "We have shown t

hat the magnitude of the largest eigenvalue decreases from approximate

ly 0.6760043 to 1." }{MPLTEXT 1 0 0 "" }}}}{SECT 0 {PARA 4 "" 0 "" 

{TEXT -1 9 "Valence 3" }}{PARA 0 "" 0 "" {TEXT -1 81 "In this case eig

envalue 1/4 is the largest and has three identical Jordan blocks." }}

{EXCHG {PARA 0 "" 0 "" {TEXT -1 8 "Block 0 " }}{PARA 0 "" 0 "" {TEXT 

-1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "jordan(subs( cs = 1, eval

(Butter00re)));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7%7%#\"

\"\"\"\"%F)\"\"!7%F+F(F)7%F+F+F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 

7 "Block 1" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "jordan( subs( cs = 1/

2, eval(Butter00re)));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#

7%7%#\"\"\"\"#;\"\"!F+7%F+#F)\"\"%F)7%F+F+F-" }}}{EXCHG {PARA 0 "" 0 "

" {TEXT -1 7 "Block 2" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "jordan( su

bs( cs = -1/2, eval(Butter00re)));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#

-%'MATRIXG6#7%7%#\"\"\"\"#;\"\"!F+7%F+#F)\"\"%F)7%F+F+F-" }}}{PARA 0 "

" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 12 "Valences \+

4,5" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 35 "K = 4; Check which formulas

 to use." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "inapply(DiscrRoot); ina

pply(cos(Pi/7)^4); inapply(cos(2*Pi/4)^2);" }}{PARA 11 "" 1 "" 

{XPPMATH 20 "6#R6\"F$6$%)operatorG%&arrowGF$7$$\"54+7Y7R?\"o[)!#?$\"5_

.7Y7R?\"o[)F+F$F$6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)oper

atorG%&arrowGF$7$$\"5hku#[=%yH*e'!#?$\"5'[YF[=%yH*e'F+F$F$6\"" }}

{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "" 0 "" 

{TEXT -1 46 "The largest eigenvalue is in the first block. " }}{PARA 

0 "> " 0 "" {MPLTEXT 1 0 48 "inapply(subs( d = cos(Pi/4)^2, AbsDominan

tEV1));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)operatorG%&arrowG

F$7$$\"5X\")HD*4A:/p%!#?$\"5s\")HD*4A:/p%F+F$F$6\"" }}}{EXCHG {PARA 0 

"> " 0 "" {MPLTEXT 1 0 48 "inapply(subs( d = cos(Pi/2)^2,AbsDominantEV

1 ));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)operatorG%&arrowGF$

7$$\"5)***************\\7!#?$\"5-+++++++]7F+F$F$6\"" }}}{EXCHG {PARA 

0 "" 0 "" {TEXT -1 6 "K = 5;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "ina

pply(DiscrRoot); inapply(cos(Pi/5)^2); inapply(cos(2*Pi/5)^2);" }}

{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)operatorG%&arrowGF$7$$\"54+7

Y7R?\"o[)!#?$\"5_.7Y7R?\"o[)F+F$F$6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 

"6#R6\"F$6$%)operatorG%&arrowGF$7$$\"5$=rtu=(\\3Xl!#?$\"5F7PZ(=(\\3XlF

+F$F$6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)operatorG%&arrow

GF$7$$\"5myGED\"G]\"\\&*!#@$\"5H!)GED\"G]\"\\&*F+F$F$6\"" }}}{EXCHG 

{PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "inapply(subs( d = cos(Pi/5)^2, AbsD

ominantEV1));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)operatorG%&

arrowGF$7$$\"5w%[1QR6cn1&!#?$\"5%>\\1QR6cn1&F+F$F$6\"" }}}{EXCHG 

{PARA 0 "" 0 "" {TEXT -1 151 "We do not have to check the eigenvalue o

f the second block: for it, d < 1/4, therefore, the magnitude of the l

argest eigenvalue is also less than  1/4." }}}}{SECT 0 {PARA 4 "" 0 "

" {TEXT -1 89 "For valence  greater than  7, the  eigenvalue  of the b

lock with m = 1 is not the largest" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 

117 "We have established that the magnitude of the largest eigenvalue \+

decreases as the function of d when d > 0.6700423 = " }{XPPEDIT 18 0 "

d[0]" "6#&%\"dG6#\"\"!" }{TEXT -1 6 ";  if " }{XPPEDIT 18 0 "d = cos(m

*Pi/K)^2 " "6#/%\"dG*$-%$cosG6#*(%\"mG\"\"\"%#PiGF+%\"KG!\"\"\"\"#" }

{TEXT -1 5 "  >  " }{XPPEDIT 18 0 "d[0]" "6#&%\"dG6#\"\"!" }{TEXT -1 

6 "\nfor  " }{XPPEDIT 18 0 "m = 2" "6#/%\"mG\"\"#" }{TEXT -1 54 ",  fo

r K > 6 we can conclude that the eigenvalue for  " }{XPPEDIT 18 0 "m= \+

2" "6#/%\"mG\"\"#" }{TEXT -1 38 "  is greater than the eigenvalue for \+

 " }{XPPEDIT 18 0 "m = 1" "6#/%\"mG\"\"\"" }{TEXT -1 30 ". This is the

 case for K > 10:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 77 " x := inapply(

2*Pi/K, K): eval(Interval_Integerpower(Interval_cos(x(11)),2));" }}

{PARA 11 "" 1 "" {XPPMATH 20 "6#7$$\"5n7K%4]1vq2(!#?$\"5'G@V4]1vq2(F&

" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 56 "For values between 7 and 10 ,

 have to check  one by one." }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 

0 "" {TEXT -1 79 "K = 7. Check which formulas to use.  Note that for m

 = 2  the  value  is below " }{XPPEDIT 18 0 "d[0]" "6#&%\"dG6#\"\"!" }

{TEXT -1 52 " , so we do not have to check the other values of m." }}

{PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "inapply(DiscrRoot); inapply(cos(Pi/

7)^2); inapply(cos(2*Pi/7)^2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"

F$6$%)operatorG%&arrowGF$7$$\"54+7Y7R?\"o[)!#?$\"5_.7Y7R?\"o[)F+F$F$6

\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)operatorG%&arrowGF$7$$

\"5>lnOH4!\\u6)!#?$\"5NlnOH4!\\u6)F+F$F$6\"" }}{PARA 11 "" 1 "" 

{XPPMATH 20 "6#R6\"F$6$%)operatorG%&arrowGF$7$$\"5u(zU=-L&R()Q!#?$\"5)

zzU=-L&R()QF+F$F$6\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 65 "In this c

ase, the largest eigenvalue is still in the first block:" }}{PARA 0 ">

 " 0 "" {MPLTEXT 1 0 48 "inapply(subs( d = cos(Pi/7)^2, AbsDominantEV1

));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)operatorG%&arrowGF$7$

$\"5f)*3b79q5>[!#?$\"5Q04b79q5>[F+F$F$6\"" }}}{EXCHG {PARA 0 "> " 0 "

" {MPLTEXT 1 0 50 "inapply(subs( d = cos(2*Pi/7)^2, AbsDominantEV1));

" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)operatorG%&arrowGF$7$$\"

5x1E&\\hNl61%!#?$\"574E&\\hNl61%F+F$F$6\"" }}}{PARA 0 "" 0 "" {TEXT 

-1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 5 "K = 8" }}{PARA 0 "> " 0 "

" {MPLTEXT 1 0 65 "inapply(DiscrRoot); inapply(cos(Pi/8)^2); inapply(c

os(2*Pi/8)^2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)operatorG%

&arrowGF$7$$\"+m=\"o[)!#5$\"+9A\"o[)F+F$F$6\"" }}{PARA 11 "" 1 "" 

{XPPMATH 20 "6#R6\"F$6$%)operatorG%&arrowGF$7$$\"+'*Q`N&)!#5$\"+<R`N&)

F+F$F$6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)operatorG%&arro

wGF$7$$\"+)*******\\!#5$\"+-+++]F+F$F$6\"" }}}{EXCHG {PARA 0 "" 0 "" 

{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "For " }{XPPEDIT 18 0 "d > \+

d[0]" "6#2&%\"dG6#\"\"!F%" }{TEXT -1 206 " , we cannot use the transce

dental expression -- intpak does not have arccosh; rather than express

ing it using logarithm, we use the algebraic expresssion, which works \+

because the discriminant is positive: " }}{PARA 0 "> " 0 "" {MPLTEXT 

1 0 71 "inapply(subs( d = cos(Pi/8)^2,op(1, [solve(ButterCharpoly, lam

bda)])));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)operatorG%&arro

wGF$7$$\"5*y>PIGnxTi%!#?$\"5>4'QIGnxTi%F+F$F$6\"" }}}{EXCHG {PARA 0 "

" 0 "" {TEXT -1 71 "We see that in this case the eigenvalue of the sec

ond block is larger: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "inapply(su

bs( d = cos(2*Pi/8)^2,AbsDominantEV1));" }}{PARA 11 "" 1 "" {XPPMATH 

20 "6#R6\"F$6$%)operatorG%&arrowGF$7$$\"5X\")HD*4A:/p%!#?$\"5s\")HD*4A

:/p%F+F$F$6\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 28 "K = 9; same resu

lt as for 8:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "inapply(DiscrRoot);

 inapply(cos(Pi/9)^2); inapply(cos(2*Pi/9)^2);" }}{PARA 11 "" 1 "" 

{XPPMATH 20 "6#R6\"F$6$%)operatorG%&arrowGF$7$$\"54+7Y7R?\"o[)!#?$\"5_

.7Y7R?\"o[)F+F$F$6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)oper

atorG%&arrowGF$7$$\"5`<!*[f:AAI))!#?$\"5o<!*[f:AAI))F+F$F$6\"" }}

{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)operatorG%&arrowGF$7$$\"5Hu^

YL))3Coe!#?$\"5bu^YL))3CoeF+F$F$6\"" }}}{EXCHG {PARA 0 "> " 0 "" 

{MPLTEXT 1 0 71 "inapply(subs( d = cos(Pi/9)^2,op(1, [solve(ButterChar

poly, lambda)])));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)operat

orG%&arrowGF$7$$\"5.v8Z.cNHWW!#?$\"5I8>Z.cNHWWF+F$F$6\"" }}}{EXCHG 

{PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "inapply(subs( d = cos(2*Pi/9)^2,Abs

DominantEV1));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)operatorG%

&arrowGF$7$$\"5\\)yB'RH2%H(\\!#?$\"5:#zB'RH2%H(\\F+F$F$6\"" }}}{EXCHG 

{PARA 0 "" 0 "" {TEXT -1 28 "K = 10, same as for 8 and 9:" }}{PARA 0 "

> " 0 "" {MPLTEXT 1 0 67 "inapply(DiscrRoot); inapply(cos(Pi/10)^2); i

napply(cos(2*Pi/10)^2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)o

peratorG%&arrowGF$7$$\"54+7Y7R?\"o[)!#?$\"5_.7Y7R?\"o[)F+F$F$6\"" }}

{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)operatorG%&arrowGF$7$$\"5!>r

tu=(\\3X!*!#?$\"5?7PZ(=(\\3X!*F+F$F$6\"" }}{PARA 11 "" 1 "" {XPPMATH 

20 "6#R6\"F$6$%)operatorG%&arrowGF$7$$\"5$=rtu=(\\3Xl!#?$\"5F7PZ(=(\\3

XlF+F$F$6\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 72 "inapply(subs

( d = cos(Pi/10)^2,op(1, [solve(ButterCharpoly, lambda)])));" }}{PARA 

11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)operatorG%&arrowGF$7$$\"5W60LnF\"*

*fG%!#?$\"54n;LnF\"**fG%F+F$F$6\"" }}}{EXCHG {PARA 0 "> " 0 "" 

{MPLTEXT 1 0 50 "inapply(subs( d = cos(2*Pi/10)^2,AbsDominantEV1));" }

}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"F$6$%)operatorG%&arrowGF$7$$\"5w%

[1QR6cn1&!#?$\"5%>\\1QR6cn1&F+F$F$6\"" }}}}{SECT 0 {PARA 4 "" 0 "" 

{TEXT -1 35 "Summary of the eigenvalue analysis " }}{PARA 0 "" 0 "" 

{TEXT -1 288 "For K = 3, the  largest eigenvalue is 1/4 and has multip

licity 7, with 2 blocks of size 2 and one block of size 3. For K = 4..

7 the largest eigenvalue has \nmultiplicity 2 and corresponds to the 1

st and the last block. For K > 7, the largest eigenvalues are not in t

he 1st and last blocks." }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 12 "Eige

nvectors" }}{PARA 0 "" 0 "" {TEXT -1 80 "Find the eigenvectors in two \+

steps.  Using the special structure of the matrix  " }{XPPMATH 2 "6#L$

7$&%\"BG6$\"\"!F(F(7$&F&6$\"\"\"F(&F&6$F,F,%'matrixG" }{TEXT -1 105 ",

  and the fact that we are interested in the eigenvectors  which are a

lso eigenvalues of  the subblock  " }{XPPEDIT 18 0 "B[0,0]" "6#&%\"BG6

$\"\"!F&" }{TEXT -1 32 ",  we find the  eigenvector as  " }{XPPEDIT 

18 0 "[ v[0], -(B[1,1]-lambda*I)^(-1) * B[1,0] *v[0] ]" "6#7$&%\"vG6#

\"\"!,$*(),&&%\"BG6$\"\"\"\"\"\"\"\"\"*&%'lambdaGF1%\"IGF1!\"\",$\"\"

\"F5F1&F-6$\"\"\"F'F1&F%6#F'F1F5" }{TEXT -1 9 ", where  " }{XPPEDIT 

18 0 "v[0]" "6#&%\"vG6#\"\"!" }{TEXT -1 24 " is the eigenvector of  " 

}{XPPEDIT 18 0 "B[0,0]" "6#&%\"BG6$\"\"!F&" }{TEXT -1 76 ".   We also \+

use the fact that in \nall cases of interest, the eigenvalues of " }

{XPPEDIT 18 0 "B[0,0]" "6#&%\"BG6$\"\"!F&" }{TEXT -1 25 " are not eige

nvalues of  " }{XPPEDIT 18 0 "B[1,1]" "6#&%\"BG6$\"\"\"\"\"\"" }{TEXT 

-1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" 

{TEXT -1 27 "Compute an eigenvvector of " }{XPPEDIT 18 0 "B[0,0]" "6#&

%\"BG6$\"\"!F&" }{TEXT -1 143 "; check first that the  two second line

s of the matrix are always independent; the second component of the cr

oss product is not zero, because  " }{XPPEDIT 18 0 "lambda >= 1/4" "6#

1*&\"\"\"\"\"\"\"\"%!\"\"%'lambdaG" }{TEXT -1 1 ":" }}{PARA 0 "> " 0 "

" {MPLTEXT 1 0 130 "crossprod( row( evalm( subs( Butterconst, evalm(Bu

tterfly00)) - lambda* &*() ), 2), row( evalm( Butterfly00 - lambda* &*

() ), 3));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'VECTORG6#7%,$*&%'lamb

daG\"\"\",&#F*\"\")F*F)!\"\"F*F.,&F)F*#F.F-F*,*#F.\"#;F*%#c|irGF2*&%\"

IGF*%\"sGF*F2*&F)F*,,#\"\"*F3F*F4#\"\"(F3*$F4\"\"#F0F5F:*(F6F*F4F*F7F*

F0F*F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 38 "Compute the first part \+

of the vector: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 126 "v0 := subs( _t[

1] = 1, map(simplify, linsolve( \n         submatrix ( evalm( Butterfl

y00- lambda*&*() ) ,2..3,1..3), [0,0] )));" }}{PARA 0 "> " 0 "" 

{MPLTEXT 1 0 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#v0G-%'VECTORG6#

7%%'lambdaG\"\"\",$*(%\"IGF*,2F-!\"\"*&F-F*%#c|irGF*F/%\"sGF**&F2F*F)F

*!\"**(F2F*F1F*F)F*\"\"#*&F-F*F)F*\"\"**(F-F*F)F*F1F6!\"#*(F-F*F)F*F1F

*\"\"(F*,&F/F*F)\"\")F/#F/F6" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 

0 53 "Butter11lambda := evalm( Butterfly11 - lambda* &*());" }}{PARA 

0 "> " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%/But

ter11lambdaG-%'MATRIXG6#7%7%,$%'lambdaG!\"\"#F,\"#;,&%#c|irGF-*&%\"IG

\"\"\"%\"sGF3#F3F.7%\"\"!,&F-F3F+F,F77%F7F7F8" }}}{EXCHG {PARA 0 "> " 

0 "" {MPLTEXT 1 0 135 "v1 := map( simplify, subs( \{ s^3 = s*(1-c^2), \+

s^2 = 1- c^2\}, map( expand, evalm( - inverse( Butter11lambda)  &* But

terfly10 &* v0 ))));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#v1G-%'VECTO

RG6#7%,$**,6%#c|irG!\"$!\"\"\"\"\"*$%'lambdaG\"\"$!%C5*&F1\"\"#F,F5\"#

kF1\"$l\"*&F1F5F,F/!$3#*&F1F/F,F/\"#X*&F1F2F,F/\"$c#*$F1F5!%?6*&F1F/F,

F5!#5F/,&F.F/F1\"\")F.,&F/F/F1\"#;F.F1F.#F.FE,$*(,8F1!#zF>!$G\"F:!#HF8

!#K*(%\"IGF/%\"sGF/F1F/!#h*(FOF/FPF/F1F5FM\"#6F/F,\"\"&*&FOF/FPF/\"\"(

**FOF/FPF/F,F/F1F/\"#=F@\"#9F/FBF.FDF.#F.F5,$*(,@F,!#6*$F,F5F5FUFhnF1

\"#hF8\"$G\"F:Fjn*(FOF/F,F/FPF/F5FWFMFN\"#z*&F,F2F1F/\"\"%F>\"#KFRF[o*

*FOF/F,F5FPF/F1F/F_oF@FM!\"(F/F/FBF.FDF.#F/F5" }}}{EXCHG {PARA 0 "" 0 

"" {TEXT -1 63 "Put the two parts of the vector together and simplify \+

notation " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 85 "ButterEigenvec

t := array( map( simplify, [seq( v0[i], i=1..3), seq(v1[i],i=1..3)])):

 " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 45 "Check if the expression make

s sense for K = 6" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 83 " map(expand, s

ubs( \{lambda = 1/2, c = 1/2, s = sqrt(3)/2\}, eval(ButterEigenvect)))

;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'VECTORG6#7(#\"\"\"\"\"#F(,&#\"

\"$\"\"%F(*&%\"IGF(F,F'#F(F-#F,F),&#\"\"&F-F(F.F0,&F(F(F.F'" }}}}

{SECT 0 {PARA 3 "" 0 "" {TEXT -1 16 "Code generation " }}{PARA 0 "" 0 

"" {TEXT -1 58 "Three functions are generated (same as for other schem

es):" }}{PARA 0 "" 0 "" {TEXT 256 23 "Float Eigenvalue(int K)" }{TEXT 

-1 28 " computes the eigenvalues, \n" }{TEXT 257 57 "void EigenvectorR

eal(Float c, Float lambda, Float* EvRe) " }{TEXT -1 68 "initializes an

 array for the real part of the complex eigenvector,  " }{TEXT 258 62 

"void EigenvectorImaginary(Float c, Float* lambda, Float* EvIm)" }

{TEXT -1 108 " initializes the array for the complex part. \nMemory fo

r arrays should be allocated by the calling function." }}{PARA 0 "" 0 

"" {TEXT -1 267 "The output is written to a file; if the name is `defa

ult`,  it is written to the standard output (warning: for some reason,

 writing to standard output is terribly slow;  writing to a file and t

hen looking at it in an editor is much more efficient. All functions u

se  " }{TEXT 259 5 "Float" }{TEXT -1 158 " as the name of the class fo

r the interval  numbers.\nIt is assumed to have explicit  casts from 6

4-bit integers,  standard arithmetics operations, and macros " }{TEXT 

260 3 "FR " }{TEXT -1 6 " and  " }{TEXT 261 4 "Fdiv" }{TEXT -1 9 ",  (

see  " }{MPLTEXT 0 21 14 "ConvertToFloat" }{TEXT -1 14 " for details).

" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "OutputFile := `butterfly

.cpp`:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "MakeClassHeader( \+

OutputFile, `Butterfly`, 2,4,3, RegButterfly):" }}}{SECT 0 {PARA 4 "" 

0 "" {TEXT -1 31 "Code generation for eigenvalues" }}{PARA 0 "" 0 "" 

{TEXT -1 307 "To show that the scheme produces C1 surfaces for valence

s 4,5,7, and not C1 surfaces for other valences we need expressions fo

r eigenvalues of the first block of the DFT-transformed subdivision ma

trix (m = 1).   \n We generate two functions, one to be used for  vale

nces 4,5,7; the other for larger valences." }}{SECT 1 {PARA 0 "" 0 "" 

{TEXT -1 2 "  " }{MPLTEXT 0 21 31 "ComputeEigenvalues(N,eps,fname)" }

{TEXT -1 459 " Numerically compute eigenvalues for a range, and write \+

a function with a large table into a file.\n  Although we have compute

d explicit formulas above,  they are numerically unstable for d close \+

to 1 (for large K);  the simplest solution is to \n  to precomute the \+

largest eigenvalue numerically with verified ; we use the fact that th

e largest eigenvalues is in the interval 1/4 .. 1 in the range of inte

rest. This function computes eigenvalues up to valence " }{MPLTEXT 0 

21 1 "N" }{TEXT -1 47 ", verifying that the precision is no less than \+

" }{MPLTEXT 0 21 3 "eps" }{TEXT -1 1 "." }}{EXCHG {PARA 0 "> " 0 "" 

{MPLTEXT 1 0 1689 "### WARNING: semantics of type `string` have change

d\nComputeEigenvalues := proc( N::integer, eps::numeric, fname::string

) \n  local K, intervCharpoly,  intervPi, intervd, \n  expandedCharpol

y, approxEV, dK;  \n  global ButterCharpoly; \n  Digits := 25;\n  inte

rvCharpoly := inapply( ButterCharpoly, lambda, d);\n  # use arccos to \+

make sure we get an interval for Pi\n  intervPi := Interval_times([2.0

,2.0],Interval_arccos([0,0]));   \n  intervd := inapply( cos(intervPi/

K)^2, K); \n  fprintf(fname, `virtual Float Eigenvalue(int K) \{\\n`);

\n  fprintf(fname, ` static INTEGER64 EV[] = \{\\n` );\n  # write  inf

inity, skip 1,2, write 3\n  fprintf( fname, `CONST64(1),CONST64(1),CON

ST64(4),\\n`);\n  fprintf( fname, `CONST64(0),CONST64(0),CONST64(0),\\

n`);\n  fprintf( fname, `CONST64(0),CONST64(0),CONST64(0),\\n`);\n  fp

rintf( fname, `CONST64(1),CONST64(1),CONST64(4),\\n`);\n\n  for K from

 4 to N  do \n    if  (K - 4) mod 100 = 0 then print(K);\n    fi;    \+

\n    dK := intervd(K);\n    expandedCharpoly := subs( d = cos(Pi/K)^2

, ButterCharpoly);\n    Digits := 25;\n    approxEV := fsolve( expande

dCharpoly, lambda, lambda=0.25..1);\n    # check that the precision is

 at least eps      \n    if  op(2, intervCharpoly(approxEV-eps, dK)) >

 0 \n       or op(1, intervCharpoly(approxEV+eps, dK)) < 0  then\n    \+

  ERROR(`fsolve precision failure for K =`, K);\n    fi;\n    Digits :

= 15; # need to get the right number of digits for printing\n    fprin

tf(fname, `CONST64(%d),CONST64(%d),CONST64(%d),\\n`, op(1,evalf(approx

EV-eps)),          op(1,evalf(approxEV+eps)),10^(-op(2,evalf(approxEV)

))); \n    Digits := 25;\n  od;\n  fprintf(fname, `CONST64(0)\};\\n re

turn Float(EV[3*K],EV[3*K+1])/Float(EV[3*K+2]) ;\\n\}\\n\\n`);\n  NULL

;\nend:   " }}}}{PARA 4 "" 0 "" {TEXT -1 0 "" }}{SECT 1 {PARA 4 "" 0 "

" {TEXT -1 20 "Generate eigenvalues" }}{EXCHG {PARA 0 "> " 0 "" 

{MPLTEXT 1 0 45 "ComputeEigenvalues( 4500, 1e-10, OutputFile):" }}}

{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 94 "optEV1 := `optimize/makeproc

`(map(ConvertToFloat,[optimize( AbsDominantEV1)]),parameters=[d]):" }}

}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" 

{TEXT -1 104 "Fix a problem with C code  generation: no return value i

s generated, if the last statement is assignment" }}{PARA 0 "> " 0 "" 

{MPLTEXT 1 0 127 "optEV1body := procbody(optEV1):\nEVstatseq := op(5,o

ptEV1body): EVstatseq :=  `&statseq`(op(EVstatseq), op(1,op(-1,EVstats

eq))):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "optEV1 := procmak

e(subsop(5=EVstatseq, optEV1body)): " }}}{EXCHG {PARA 0 "> " 0 "" 

{MPLTEXT 1 0 121 "S := []: C(optEV1,ansi): \nfor i from 1 to vectdim(S

) do \n  fprintf(OutputFile, replaceall(op(i,S),`double`,`Float`)):\no

d:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 33 "Second version for valences

 >= 8;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 116 "optEV2 := `optimize/make

proc`(map(ConvertToFloat,[optimize( op(1,[solve(ButterCharpoly,lambda)

]))]),parameters=[d]):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "o

ptEV2body := procbody(optEV2):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 95 "E

Vstatseq := op(5,optEV2body): EVstatseq :=  `&statseq`(op(EVstatseq), \+

op(1,op(-1,EVstatseq))):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 

"optEV2 := procmake( subsop(5=EVstatseq, optEV2body)):" }}}{EXCHG 

{PARA 0 "> " 0 "" {MPLTEXT 1 0 121 "S := []: C(optEV2,ansi): \nfor i f

rom 1 to vectdim(S) do \n  fprintf(OutputFile, replaceall(op(i,S),`dou

ble`,`Float`)):\nod:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}

}{EXCHG {PARA 0 "" 0 "" {TEXT -1 117 "This function is used to constru

ct interval eigenvectors  \"at infinity\";  assume d  sufficiently clo

se to 1, so that " }{XPPEDIT 18 0 "lambda(c)" "6#-%'lambdaG6#%\"cG" }

{TEXT -1 11 " decreases." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 409 "fprint

f( OutputFile,  `virtual void EigenvalueRange( Float c, Float& lambdam

in, Float& lambdamax) \{\\n`):\nfprintf( OutputFile,  `Float d = FR(1,

2)*(c + Float(1)); assert( (exactfloor(d)).as_double() > 0.676);\\n`):

  \nfprintf( OutputFile,  `if( exactceil(c)  < exactfloor( sqrt(Float(

2))/Float(2)) )\\n`):\nfprintf( OutputFile,  `lambdamax = optEV1(d);\\

n  else lambdamax = optEV2(d); lambdamin = FR(1,4);\\n\}\\n\\n`):" }}}

{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{SECT 1 {PARA 4 "" 0 "

" {TEXT -1 33 " Code generation for eigenvectors" }}{PARA 0 "" 0 "" 

{TEXT -1 183 "Two functions are generated; one initializes an array fo

r the real part of the complex eigenvector, the other for the complex \+

part. Memory should be allocated by the calling function." }}{PARA 0 "

" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "Gener

ateEigenvectorCode(ButterEigenvect, OutputFile);" }}}{EXCHG {PARA 0 ">

 " 0 "" {MPLTEXT 1 0 26 "fprintf(OutputFile, `\};`):" }}}{EXCHG {PARA 

0 "> " 0 "" {MPLTEXT 1 0 19 "fclose(OutputFile);" }}}}{PARA 0 "" 0 "" 

{TEXT -1 0 "" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 25 "Modified Butterf

ly scheme" }}{PARA 0 "" 0 "" {TEXT -1 151 "The Modified Butterfly sche

me by construction always has the subdominant eigenvalue 1/2  in the f

irst block of the DFT-transformed subdivision matrix. " }}{PARA 0 "" 

0 "" {TEXT -1 122 "Thus, we only need to compute the eigenvectors for \+

 the characteristic map analysis.  We do not assume that w = 1/16 here

." }}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 31 "Compute the complex eigenvec

tor" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 338 "ModButter := matrix(

 [ \n [ 1/2, 0, 0,0,0,0],\n [1,0,0,0,0,0],\n [(1/2)*(1+ omega) - w*(co

njugate(omega) + omega^2 ), -w*(1 + omega),2*w,0,0,0], \n [1/2 - 2*w*c

,1/2,2*w*(1+conjugate(omega)),0, -w, -w*conjugate(omega)],\n [1/2 + 2*

w*omega, 2*w - w*omega,1/2-w*conjugate(omega),0,-w,0], \n [(1/2)*omega

 + 2*w,2*w*omega-w, 1/2 - w*omega,0,0,-w]]);" }}{PARA 11 "" 1 "" 

{XPPMATH 20 "6#>%*ModButterG-%'MATRIXG6#7(7(#\"\"\"\"\"#\"\"!F-F-F-F-7

(F+F-F-F-F-F-7(,(F*F+%&omegaGF**&%\"wGF+,&-%*conjugateG6#F1F+*$F1F,F+F

+!\"\",$*&F3F+,&F+F+F1F+F+F9,$F3F,F-F-F-7(,&F*F+*&F3F+%#c|irGF+!\"#F*,

$*&F3F+,&F5F+F+F+F+F,F-,$F3F9,$*&F3F+F5F+F97(,&F*F+*&F3F+F1F+F,,&F3F,F

KF9,&F*F+FHF9F-FFF-7(,&F1F*F3F,,&FKF,F3F9,&F*F+FKF9F-F-FF" }}}{EXCHG 

{PARA 0 "" 0 "" {TEXT -1 45 "This is simple enough for the Maple funct

ion." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "jordan(ModButter,`P`);" }}

{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7(7(#\"\"\"\"\"#\"\"!F+F+F

+F+7(F+,$%\"wG!\"\"F+F+F+F+7(F+F+,$F.F*F+F+F+7(F+F+F+F+F)F+7(F+F+F+F+F

+F+7(F+F+F+F+F+F-" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 145 " ModB

utterEigenvect := subs( \{ w = 1/16, cos(2*m*Pi/K) = c, sin(2*m*Pi/K) \+

= s\}, map( simplify, map( evalc, subs( Buttervar, col(eval(`P`),1))))

);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%3ModButterEigenvectG-%'VECTORG

6#7(\"\"\"\"\"#,,*$%#c|irGF*#!\"\"\"\"$#\"\"(\"\"'F)F-#\"\"&F3*(%\"IGF

)F-F)%\"sGF)F.*&F7F)F8F)F1,(#\"$`'\"$;#F)F,#!#6\"$3\"F-#F)F=,,F-#\"#N

\"#aF,#!\"(\"#F#\"$@\"FEF)F9F1F6F.,0*$F-F0#F*FHF-#\"$.\"FEF,#!#9FHF1F)

*(F7F)F8F)F-F*FMF9FIF6FP" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 15 "Cod

e generation" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "OutputFile :

= `modbutterfly.cpp`:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "Ma

keClassHeader( OutputFile, `ModButterfly`, 2,4,3, RegButterfly):" }}}

{EXCHG {PARA 0 "" 0 "" {TEXT -1 43 "Write a trivial function for the e

igenvalue" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 97 "fprintf( OutputFile, `

virtual Float Eigenvalue( int K ) \{\\n  return Float(1)/Float(2);\\n

\}\\n\\n` ):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 146 "fprintf( O

utputFile, `virtual void EigenvalueRange( Float c, Float& lambdamin, F

loat& lambdamax) \{\\n  lambdamin = lambdamax =  FR(1,2);\\n\}\\n\\n` \+

):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "GenerateEigenvectorCo

de(ModButterEigenvect, OutputFile):" }}}{EXCHG {PARA 0 "> " 0 "" 

{MPLTEXT 1 0 26 "fprintf(OutputFile, `\};`):" }}}{EXCHG {PARA 0 "> " 

0 "" {MPLTEXT 1 0 19 "fclose(OutputFile):" }}}{EXCHG {PARA 0 "> " 0 "

" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}

}}{MARK "9" 0 }{VIEWOPTS 1 1 0 1 1 1803 }