チェビシェフ展開係数を用いたスツルム算法による実代数方程式の実根の分離

全文

(1)Vol.2009-HPC-122 No.4 2009/10/9. ᑔ༲େᾤძॗ∩⎇༲೸ IPSJ SIG Technical Report. ߫ᅟߙࠋ྽㑦ጟ߮ਓࠒࢬ߈ࠋᕞ░ߍߨߗߦࢬ߈ࠉࠌࠋ༴ೋ߯㡸ᤐࠒᮀࠁߟ߄ᄗఽ㋨߫ᝫ߄ߦ ྽㑦ጟࠒ࠼ࠢࡎ࠲ࠢࡐⰎ㋨߫ࠈࠊ࠼ࠢࡎ࠲ࠢࡐ৉᜼ߧ⯍ᾝߗߦ㡸ߝࠌߋࠉᤐࠒᮀࠁࠋ߮ߌ⡁. ϴϚІϪϚЈൾ⻅֫ጠψᰰͺΕϬϷОГ†ៀΡξρ ೺ԓጠፎἥ༃Τ೺ᓴΤ݄⾒. ߄㡺ᡊ୯߫ߓ߮࠼ࠢࡎ࠲ࠢࡐᆛ㋡߮৉᜼ࠒ㡴ᎨⱲߪࠉ㗀⓸ዕⲺ␼߫ࠈࠊ㡵⓸ዕ⡁ߏᮀࠁߦ♰ ߏߓߨߌㄢⱲߧ߂ࠋ㡺㡴ᄗఽ㋨ଁߧ࠼ࠢࡎ࠲ࠢࡐᆛ㋡ߕࠌߟ㗀᫖ऱ᜼ᝪ⍁ጟ߮ᤐࠒ྽᜼ᮀࠁ ࠋඋ㒖߮๹ᡏਓඋ㒖߸߮Ꮈ⁌তߨߗߦⵒᝈ1) ࠒᙀߒߦߊߏ㡺㡵. ᡽. ࢨ. ጧ†1. 㡴྽㑦ጟߧ߯ߪ߄᳸ࠉߋߪ㋲᜼߮ᝪ⍁ጟ߫ߤ߄ߦࠂ㡸㎸ᷲࠒᮀࠁߟ߄㑶༂ଁߧ࠼ࠢࡎ࠲ࠢ ࡐ྽㑦ጟ߫ࠈࠋᆛ㋡ࠒ⮷߆ߨ㡸ᆛ㋡ߕࠌߟんୡഞ߯Ꮹ〈߫૔߮㋲᜼߫࢟᨟ಠᢆߗ㗀᫖㑦߮৉ ᜼߯Ꮹ᲍ᅯߙࠋ߮ߧ㡸ౄୡ࿆߫ߍߪ᫖᜼ N ߾ߧߧᆛ㋡ࠒᕥߡୢߣߦ஢ॿ㑦んୡࠒḗⲀߙࠋ. ᡊ୯߫ᄗऱ᜼ᝪ⍁ጟࠒ㡸ᄗᤐࠒᮀࠁߟ߄ᄗఽ㋨ଁ߫ᝫߑࠋ࠼ࠢࡎ࠲ࠢࡐ྽㑦ጟࠒ⁌ ߄ߟᆛ㋡፞ߧ⯍ߙ㡺ߝࠌ߫ᅟߗߦ࠼ࠢࡎ࠲ࠢࡐ৉᜼⯍ᾝࠒ⁌߄ߟ࠴࠿ࡦ࡛୭߮ᨖᔴࠒ ⮷ߪ߄㡸࠴࠿ࡦ࡛߮ᄓᾤ߫༒ߥ߄ߦᄗᤐ߮ࠦࠡ࡮ࡃࠄୡ㎮ࠒ⮷߆㡺ߓ߮ᝪᯜ߮᜼ਓᄗ 㕰ࠒ╍ञߙࠋ㡺. ߓߨߧ㡸㋲᜼ࠒ྽㑦ጟߧ࢟᨟߫⿏१ߙࠋߓߨߌߧߍࠋ㡺ߝ߮྽㑦ጟ߮㎸ᷲߧ૔߮㋲᜼߯ᅮߕ ߄ᬙቨࠒᗏߤ㡺ߗߋߗ㡸ఽ㋨߮ࢿ߫㎸ᷲࠒᮽᆮᗏߤࠈ߆ߪᗧ௫ℽߪ㋲᜼߮༴ೋ߫߯㡸㎸ᷲ߮ ৼ᜼߫ᭉতߙࠋ㡴᜼৾⍁ዕ߮㡵ৼ᜼߮ᆛ㋡㑦ࠒ⁌߄ߪߑࠌ߰ౄୡߪ⿏१ߌ୘ᢌߪ߄㡺㡵 झ๥߯㡸ᰭ௫ᅮ᜼ᷲ᜼ᴘ␼ࠒ⁌߄ߦ㡸ಲૺℽߪ࠴࠿ࡦ࡛߮ᝪᯜ4) ߫༒ߥ߄ߦᩃ᳒ఽ㋨. Sturm Method using Chebyshev Expansion Coefficients for Real Root Isolation of Real Algebraic Equations. [−1, 1] ଁ߮࠼ࠢࡎ࠲ࠢࡐᆛ㋡߮৉᜼ߧࢬ߈ࠉࠌߟᄗ྽㑦ጟ߮ऱ᜼ᝪ⍁ጟ߮िᒊ߮ᄗఽ㋨ [a, b](⊂ [−1, 1]) ଁ߫߂ࠋᄗᤐ߮ৼ᜼ࠒᮀࠁࠋᝪᯜߨ㡸ߝࠌࠒଇ኎ℽ߫୵⁌ߗߦᄗᤐ߮ୡ㎮ ࠒ⮷ߪ߆ᝪᯜ߮ᄗ㕰ߗߟতࠒ╍ञߙࠋ㡺࠴࠿ࡦ࡛୭ࠒংࠋߟࠁ߮྽㑦ጟ஢ॿ߮Ⲻ␼߫ᝫ߄ߦ. Hiroshi Murakami†1. ߯㡸྽㑦ጟ߯૯ߦ࠼ࠢࡎ࠲ࠢࡐ৉᜼ࠒ⁌߄ߦ⯍ᾝߙࠋ㡺. 1.1 ϴϚІϪϚЈൾ⻅ΡξρᓴψᝤηρԇΤፎៀΤֆ. At first, a given real algebraic equation is represented by a Chebyshev polynomial expansion inside the real interval to search the roots. From the polynomial, the Sturm sequence is constructed, all polynomials in the sequence are represented by the Chebyshev coefficients. Then the counting and the isolation of real roots are made by the use of Sturm’s theorem. Some numerical experiments of this method are shown.. • ࠼ࠢࡎ࠲ࠢࡐᆛ㋡ࠒ୵⁌ߗߟᄗᝪ⍁ጟ߮ᄗᤐ߮Ⲻ␼߮তߨߗߦ߯㡸ত߈߰ᝈἤ7)–9) ߪ ߩߌ߂ࠋ㡺߾ߟ࠼ࠢࡎ࠲ࠢࡐᆛ㋡ߧ⯍ߕࠌߟ྽㑦ጟ߫ᅟߗߦ߯㡸ߝ߮࢟⠚ట㍲य़⮷୭߮ ๹ᡏਓߨߗߦᎨⱲߪࠉ૯ߦ߮ᤐࠒ㡴Ⱖ┽ᤐࠂ㡵ᮀࠁࠋߓߨߌಽ❝ߧ߂ࠋ㡴७ߗ㡸ᆛ㋡༒ ዌ߮࠼ࠢࡎ࠲ࠢࡐ྽㑦ጟ߮ᄓ⚗ఽ㋨ࠒೡࠀ⿏੕߮ྺ߮ᤐ߮⿏१⓸ዕ߯⡁ߏߪ߄㡵㡺࠼ࠢ ࡎ࠲ࠢࡐᆛ㋡߫ᅟߙࠋ࢟⠚ట㍲य़⮷୭߮ࡓ࠾࠶࡮ࡔࡦࠫᏫ߫ࠈࠊ㡸ᩃ᳒ℽߪ QR ಟ᎖ ᯜࠒↇᘵচ⁌ߗߦ૯๹ᡏਓࠒᮀࠁࠋⲺ␼ㄤ߯ᝪ⍁ጟ߮᫖᜼ N ߫ᅟߗߦ O(N 3 )㡸ⳇᓻㄤ. 1. Υ Ύ η Ρ. ߯ O(N 2 ) ߧ߂ࠋ14) 㡺࢟⠚ట㍲य़⮷୭߮ₛ⮷୭߮ᨖ〉߫Ệటߗߟ QR ಟ᎖ᯜߧ૯๹ᡏ ਓ߮Ⲻ␼ㄤߌ O(N 2 ) ߮ࠂ߮6) ߌ߂ࠋ㡴ߗߋߗ᜼ਓℽᄃᄓᏫ߫㎯ᷲߌ߂ࠋࠈ߆ߧ߂ࠋ㡵㡺. 㗀᫖߮ᄗऱ᜼ᝪ⍁ጟ߮ᄗఽ㋨ଁ߮ᄗᤐࠒᮀࠁࠋⲺ␼߫ᝫ߄ߦ㡸ᝪ⍁ጟ߮྽㑦ጟࠒఽ㋨ଁߧ. QR ಟ᎖ᯜ߮࠲ࡐࡃᛕংࠒ୽᎑ߗߦᎨⱲߪ⑚๴߮๹ᡏਓߠߑࠒぎᖒℽ߫ಠᢆߕߛߦᮀࠁ. ᆛ㋡ߙࠋ༒ዌߨߗߦ࠼ࠢࡎ࠲ࠢࡐ྽㑦ጟࠒ⁌߄ࠋߨ㡸ᤐ߮ᢈऽ᜼㡴৉᜼߮ྰట߫ࠈࠋᤐ߮ਓ ߮ᜨᒘߕ㡵ߌౕ㑦ጟࠒᆛ㋡༒ዌ߫⁌߄ࠋ༴ೋ߫ᭉ߹ߦᅮߕ߄߮ߧ. 10)–13). ࠋᝪᯜ߮ಽ❝Ꮻ߫ߤ߄ߦ߯झᎂ߮ⴸ㒖ߧ߂ࠋ㡺. 㡸ᤐࠒᰭ௫ᅮ᜼ᴘ␼. • ࢟⠚ట㍲य़⮷୭߮ߔߏᅯ᜼߮๹ᡏᅟߧ㡸ቺᡚߗߟ㑶༂ध⿏߫๹ᡏਓߌ߂ࠋࠂ߮ߠߑࠒぎ. ߧᮀࠁࠋ༴ೋ߫ࣇࠁⴭቨ߮፪㑢ߌᅯߪ߄ߓߨߌᡞ፼ߧߍࠋ㡺Ệ߫㡸㗀᫖߮ᄗ྽㑦ጟߌ㡸ጤ᜼. ᖒℽ߫ᮀࠁࠋᕞᯜߨߗߦ㡸ࡧࠟࡥࡷඅधߍ߮⿴ಟ᎖ᯜ㡸ࡥ࠾࠿ਓࠒ࠲ࡐࡃ߫⁌߄ߟ೏៊ ⿴ಟ᎖ᯜ14),16) 㡸ࡐࠞࡦ࠺ᅟⲜటᯜ2),3) ߪߩߌ⛊߈ࠉࠌ㡸ߓࠌࠉ߯࢟⠚ట㍲य़⮷୭߮ₛ. †1 㔤゜࿆ძᢔऍ ᜼ᾤᑔ༲⌞ძᅢ᜜ Department of Mathematics and Information Sciences, Tokyo Metropolitan University. ߪᨖ〉߫இߗߟỆ୲ߪ LU ୡⲥ߂ࠋ߄߯ QR ୡⲥࠒ⁌߄ࠋߓߨ߫ࠈࠊ㡸ᝪ⍁ጟ߮᫖᜼. 1. c 2009 Information Processing Society of Japan .

(2) Vol.2009-HPC-122 No.4 2009/10/9. ᑔ༲େᾤძॗ∩⎇༲೸ IPSJ SIG Technical Report. N ߫㋲ߗߦⲺ␼ㄤߨⳇᓻㄤ߮ࢸᝪߌ O(N ) ߫ߪࠋ㡺ߗߋߗ㡸ᮀࠁߟ߄๹ᡏਓ߮ৼ᜼ r. ጟ߮ਓࠒᮀࠁࠋߓߨ߯㡸࠼ࠢࡎ࠲ࠢࡐ྽㑦ጟ߮ࢧ㑦ᴭటጟ߫༒ߥߏ㡴ౕ㑦ጟ߮༴ೋ߮ Horner. ߌ㏸ኔ߫྽ߏߪࠋߨ㡸ⳇᓻㄤߌ r ߫ᭉতߗߦཫ௃ߗ㡸Ⲻ␼ㄤࠂ O(r) ৼ߮ࡔࠪࡃࡦ߮ↇ. ␼ᯜߨ㒥१߮㡵Clenshaw ߮␼ᯜ㡴੘ 1㡵ࠒ⁌߄ߦⲺ␼ㄤ O(N ) ߧߧߍࠋ㡺ߓ߮Ⲻ␼ߧᮀࠁ. ईటߪߩ߫ࠈࠊ㡸Ⲻ␼ㄤߌ O(r 2 N ) ߮んୡߌુ⺉ߗߦ㡸๲㎯ߌ⁄ߘࠋ㡺. ߟ࠴࠿ࡦ࡛୭߮Ⱳᮀߕࠌߟୡᷲߧ߮ਓ㡸ߝ߮⏵ೄߋࠉ⏵ೄྰట᜼ࠒᮡᄓߗߦ࠴࠿ࡦ࡛߮ᄓᾤ ࠒぃ⁌ߙࠋ㡺. 2. ϬϷОГΤ೶ᮈΡξρ೺ᓴΤጠ;ҊΈ N ᫖྽㑦ጟ F (x) ߫ᅟߗ㡸F0 =F (x) ߨ F ߮ᅭ㋲᜼ F1 =F (x) ߋࠉဲࠁߦ㡸஢ॿ߮⏵ೄ. qN+2 := 0 ; qN+1 := 0 ;. ࠒಟ⽋ߗߟ྽㑦ጟ߮୭ Fk = − remainder(Fk−2 , Fk−1 ) ࠒংࠊ㡸㎸྽㑦ጟ߫ߪࠋↇ஌߾ߧ. for j := N step −1 until 1 do qj := 2 * x * qj+1 − qj+2 + fj od ;. ߮྽㑦ጟ߮୭ {F0 , F1 , . . . , FM } ࠒ F ߮࠴࠿ࡦ࡛୭ߨ߄߆㡺M ≤N ߧ߂ࠋ㡺FM ߯⏵ೄࠒ. q0 := x * q1 − q2 + f0 ;. ㍒ߑ߰ GCDx (F (x), F (x)) ߫␎ߗ߄㡺⏵ೄྰట᜼ V (x) ߯㡸࠴࠿ࡦ࡛୭߮ x ߫ᝫߑࠋਓ. return q0. {F0 (x), F1 (x), . . . , FM (x)} ࠒ㡸ਓ 0 ࠒ↏߄ߦባߋࠉ㑧߫ⱹߦ߄ߏߨߍ߮⏵ೄ߮ྰట߮๥᜼ߧ. ੘1. ߂ࠋ㡺ߝ߮ߨߍఽ㋨ ( α, β ] ߧ߮ F (x) ߮ᄗᤐ߮ৼ᜼߯㡴ㄢᤐ߯ 1 ৼߨ᜼߈ߦ㡵V (α) − V (β). Clenshaw ߮␼ᯜ. ߧࢬ߈ࠉࠌࠋ㡺ߓࠌ߫ࠈࠊ౾ᾤࢨ߯ఽ㋨ଁ߮ᄗᤐ߮ৼ᜼ߌᮀ߾ࠋ㡺७ߗఽ㋨߮⏗ᷲ x=α ߌ. F (x) ߮ k ㄢᤐ (k > 1) ߮༴ೋ߯㡸࠴࠿ࡦ࡛୭ࠒ (x − α)k−1 ߧ૙߫தߣߦߋࠉ V (α) ࠒᮀࠁ. 3.3 ൐⻖ጠΤϴϚІϪϚЈൾ⻅֫ጠ. ࠋ㡺x=β ߮༴ೋࠂ೏᨟ߨߙࠋ㡴α ࠄ β ߌㄢᤐߧߪߑࠌ߰㡸ߓߓ߮ᯪᒊ߯ࢫⱲߧ߂ࠋ㡵㡺ఽ. ࠼ࠢࡎ࠲ࠢࡐ྽㑦ጟ Tk (x) ߮ᅭ㋲᜼߯ kUk−1 (x)㡸७ߗ U (x) ߯ ᫖߮⏻ࣵ⍕࠼ࠢࡎ࠲ࠢ. ㋨◹ᅮᯜࠒ⁌߄ࠋߨᄗᤐ߮ୡ㎮ࠄ⿏१⓸ዕࠒ㗀ࠁࠋߓߨߌߧߍࠋ㡴ಗ⛊ᝈἤ4) 㡵㡺. ࡐ྽㑦ጟߧ߂ࠋ㡺㋲৉ጟ Uk (x) ≡ 2Tk (x) + Uk−2 (x)㡸U1 (x) ≡ 2T1 (x)㡸U0 (x) ≡ T0 (x) ࠒ⁌߄ࠋߨ5) 㡸⏻ࣵ⍕࠼ࠢࡎ࠲ࠢࡐ྽㑦ጟ߫ࠈࠋᆛ㋡߯ᄬឦ߫㡴⏻࢟⍕㡵࠼ࠢࡎ࠲ࠢࡐ྽㑦. 3. ϴϚІϪϚЈ஠お༃. ጟ߫ࠈࠋᆛ㋡߸ྰᙘߧߍࠋ㡺ᆛ㋡৉᜼ fk 㡸k=0, . . ., N ࠒᗏߤ N ᫖྽㑦ጟ F (x) ߮ᅭ㋲᜼. G(x) = F (x) ߮৉᜼ gk 㡸k=0, . . ., N −1 ߯㡸੘ 2 ߮␼ᯜߧⲺ␼ߧߍࠋ㡺. ࠼ࠢࡎ࠲ࠢࡐ྽㑦ጟ߯㋲᜼߮ఽ㋨ [−1, 1] ߧ߮࢟᨟⿏१߫ᡊࠂ৆୵ߪↇई྽㑦ጟߧ߂ࠋ㡺k ᫖߮྽㑦ጟ Tk (x) ߯ࢧ㑦ᴭటጟ T0 (x)=1㡸T1 (x)=x㡸Tk+1 (x)=2xTk (x) − Tk−1 (x) ߫ࠈࠊ ⁄ᔴߕࠌ㡸ࢧⲜ㋲᜼ߨ Tk (cos θ)= cos(kθ) ߧ㋲৉ߗߦ߄ࠋ. 5),19). 3.4 ϴϚІϪϚЈൾ⻅Ρξρ஠お༃Τ‫ޅ‬ա⢞† m ᫖྽㑦ጟ A(x) ࠒ n ᫖྽㑦ጟ B(x) ߧ㍒␼ࠒߗߟ஢ॿࠒ R(x) ߨߙࠋ㡺A(x)㡸B(x) ߮. 㡺. 3.1 ϴϚІϪϚЈൾ⻅. ࠼ࠢࡎ࠲ࠢࡐᆛ㋡৉᜼߮ニ୭ࠒ a(0:m)㡸b(0:n) ߨߗ㡸㗀‫(ޢ‬n−1) ᫖߮஢ॿ྽㑦ጟ R(x) ߮. N ᫖ᄗ৉᜼྽㑦ጟ P (t) ߮ᄗᤐࠒᮀࠁߟ߄ t ߮ఽ㋨ [a, b] ࠒ x ߮ᩃ᳒ఽ㋨ [−1, 1] ߫ྰ᜼߮࢟. ࠼ࠢࡎ࠲ࠢࡐᆛ㋡৉᜼߯ニ୭ a(0:n-1) ߮んୡ߫ㄢ߭ᡂߍߙࠋࠂ߮ߨߙࠋ㡺╗⎻㍒ᯜ߫ࠈࠋ. ᫖ྰᙘߧᅟᎸߕߛߟࠂ߮ࠒ F (x)=P (t) ߨߙࠋ㡺x ߮ N ᫖྽㑦ጟ F (x) ࠒᩃ᳒ఽ㋨ [−1, 1] ଁ. த␼߯㡸࠼ࠢࡎ࠲ࠢࡐ྽㑦ጟ߮⍯߮૳ጟ Tm (x)·Tn (x) = (1/2)(Tm+n (x) + T|m−n| (x)) ߫ࠈ. ߧ࠼ࠢࡎ࠲ࠢࡐ྽㑦ጟ Tk (x) ߧᆛ㋡ߙࠋ:F (x)=. f T (x)=f0 T0 (x) + f1 T1 (x) + · · · + k=0 k k. 㡴ᯪ: ⳇ ࠊ㡸ং᧜ニ୭ h(0:m) ࠒ⁌߄ࠌ߰㡴Fortran90 㒥१߮ⳇᯜߧ㡵੘ 3 ߮ࠈ߆߫ᡂߑࠋ㡺. fN TN (x)㡺྽㑦ጟ߮ (N + 1) ৼ߮ぎᷲ x = − cos{( − 1/2)π/(N + 1)}㡸=0, . . ., N ߫ᝫ. ᓻㄤࠒஉ᲍ߙࠋ༴ೋ߫߯ং᧜ニ୭ࠒচࠏߪ߄߻߆ߌ⡁߄㡺㡵࠴࠿ࡦ࡛୭ࠒংࠋ༴ೋ߮஢ॿⲺ. N. ߑࠋਓ F (x ) ߋࠉ࠼ࠢࡎ࠲ࠢࡐ৉᜼ fk ࠒᮀࠁࠋᛕংಜ߳ߝ߮⿴ᛕং߮Ⲻ␼ㄤ߯㡸ౕ┲ߪᝪ ᯜߧ߯ O(N 2 ) ߠߌ㡸⡁ߏ∐ࠉࠌߦ߄ࠋࠈ߆߫㗀〈㎮᜷࠮࠰ࠟ࡮ྰᙘ㡴FDCT㡵ࠒ⁌߄ࠋߨ. for k := 1 to N do gk−1 := k * fk od ;. O(N log N ) ߫ߧߍࠋ15) 18) 㡺ळࢩߧ߯྽㑦ጟ߯ᡊ୯ߋࠉ࠼ࠢࡎ࠲ࠢࡐᆛ㋡߮৉᜼߫ࠈࠊࢬ. for k := N −1 step −1 until 2 do gk−2 := gk−2 + gk ; gk := 2 * gk od ;. ߈ࠉࠌࠋࠂ߮ߨߙࠋ㡺. g1 := 2 * g1. 3.2 ϴϚІϪϚЈൾ⻅΋ςΕ஠お༃Τ‫׶‬Τ⢞†ៀ N ᫖྽㑦ጟ F (x) ߮࠼ࠢࡎ࠲ࠢࡐᆛ㋡߮৉᜼ fj 㡸j=0, . . ., N ߋࠉ㡸ୡᷲ x ߫ᝫߑࠋ྽㑦. ੘2. 2. ࠼ࠢࡎ࠲ࠢࡐᆛ㋡ߕࠌߟ྽㑦ጟ߮ᅭ㋲᜼ࠒᮀࠁࠋ␼ᯜ߮ত. c 2009 Information Processing Society of Japan .

(3) Vol.2009-HPC-122 No.4 2009/10/9. ᑔ༲େᾤძॗ∩⎇༲೸ IPSJ SIG Technical Report. ߪ߄㡺. IF (m < n) THEN RETURN DO k = m, n, −1 i = k−n h(0 : k) = 0.0 DO j = 0, n t = 0.5 * b(j) ; h(i + j) = h(i + j) + t ; h(ABS(i − j)) = h(ABS(i − j)) + t ENDDO q = a(k) / h(k) a(0 : k−1) = a(0 : k−1) - q * h(0: k−1) ENDDO a(n : m) = 0.0 ੘3. • ⏵ೄྰట᜼ࠒᮀࠁߟ߄ୡᷲ߮╗ {x1 , x2 , . . . , xp } ߫ᅟᎸߙࠋ࠴࠿ࡦ࡛୭߮⏵ೄྰట᜼߮ ╗ {V (x1 ), V (x2 ), . . . , V (xp )} ࠒᮀࠁࠋ㍻߫㡸࠴࠿ࡦ࡛୭૯ॹࠒ߂ࠉߋߘࠁ࢟ዕ⁄ᔴߗ ߦয়ᗏߙࠋߔߏ⟦Ḟߪᝪᯜߧ߯ⳇᓻㄤ߯ O(N 2 ) ߨߪࠋߌ㡸࠴࠿ࡦ࡛୭߮૯ॹࠒয়ᗏߛ ߚ߫ळࢩ߮ࠈ߆߫ߙࠋߨ㡸ⳇᓻㄤࠒ O(N ) ߫ॴ᲍ߙࠋߓߨߌಽ❝ߧ߂ࠋ㡺ߝࠌ߯㡸࠴࠿ ࡦ࡛୭߮྽㑦ጟࠒ㑧₁߫⁄ᔴߗߦ߄ߏ㍻߫㡸૔߮྽㑦ጟ F ≡F0 ࠒᓻ߈ߦߊߏⳇᓻ༴ᕕ ळྺ߫ 2 ৼ߮྽㑦ጟࠒয়ᗏߧߍࠋⳇᓻ༴ᕕߠߑࠒ≷য়ߗ㡸྽㑦ጟ Fi−2 ࠒ྽㑦ጟ Fi−1 ߧதߣߟ஢ॿࠒ Fi−2 ߮༴ᕕ߫ㄢ߭ᡂߍߗߦংࠋ㡺ߝ߮〬⍁ߨߨࠂ߫㡸߂ࠉߋߘࠁᗓᄓ ߕࠌߟୡᷲ x1 , x2 , . . . , xp ߫ᝫߑࠋ⏵ೄྰట᜼ࠒ㡴ᗓᄓߕࠌߟୡᷲ߫ᝫߑࠋ㑧᫖߫⁄ᔴ ߕࠌߦ߄ߏ྽㑦ጟ Fi ߮ਓ Fi (x1 ), Fi (x2 ), . . . , Fi (xp ) ࠒᮀࠁߦߝ߮⏵ೄࠒୱᄓߙࠋߓߨ. ࠼ࠢࡎ࠲ࠢࡐ৉᜼ࠒ⁌߄ߟ྽㑦ጟ߮஢ॿⲺ␼ᯜ߮ত. ߧ㡵ᠿᝥߗߦ߄ߏ㡺ߓ߮ᝪᯜߧ߯ᎨⱲߪⳇᓻㄤ߯ O(N ) ߫ߪࠋ㡺 ␼߯㡸ᬖࠓߩ૯ߦ߮༴ೋ߫ߤ߄ߦ㡸᫖᜼ߌ 1 ߚࠌߟ྽㑦ጟ೏ྟߧத␼ࠒ⮷ߪ߆ߓߨ߫ߪࠋ㡺. 5. ೺ ㅔ ֆ. 4. ϬϷОГៀΡξρ೺ᓴΤ݄⾒Ξ⮳ՉΤູ⃜ࢷҊ. ࠲࠴ࡁ࡛߮⵫૔߯㡸CPU ߯ Intel Core i7 920(2.67GHz) ߧ 1 ࠮ࠝߠߑচ⁌㡸࡜࡝ࡥ. ࠴࠿ࡦ࡛߮ᄓᾤ߫ࠈࠊिᒊ߮ఽ㋨ [a, b] ଁ㡴७ߗ࠼ࠢࡎ࠲ࠢࡐ྽㑦ጟ߮ᩃ᳒ఽ㋨߫ೡ߾ࠌ. ߯ DDR3-1333 ߮ 2Gbyte×6 ᡦ=12Gbyte(triple channel)㡸࠮࡮ࡌࠟࡤ߯ intel Fortran. ߦ߄ࠋߨߙࠋ㡵ߧ߮ᄗᤐ߮ৼ᜼ߌᮀࠁࠉࠌࠋ߮ߧ㡸ఽ㋨߮ଇ኎ࣵୡத␎ࠒ⁌߄ߟᄗᤐ߮ୡ㎮. ver11.1 for intel64(ࠥࡒ࠲ࡢ࡮ -fast)㡸OS ߯ Fedora 11 for x86 64㡸ࡂࡷ࠺ߨᴘ␼߮᜼. ࠄ⓸ዕ೔ࢨߌಽ❝ߧ߂ࠋ㡺. ਓ߯ IEEE 64bit ৾⓸ዕᰭ௫ᅮ᜼ᷲ᜼ߧ߂ࠋ㡴Intel Fortran ߫੟ࠏߣߦ߄ࠋ๢৾⓸ዕᴘ␼. ࠂߗࠂ࠴࠿ࡦ࡛ࣵୡᯜࠒౕỽߧᡊᎂ߾ߧ⁌߄ߦ૔߮ఽ㋨ଁ߮ᄗᤐࠒ૯ߦỾ߄ఽ㋨߫߾ߧ. 㡴128bit㡵ࠒ⁌߄ߦⲺ␼ࠒ⮷ߪߣߟ༴ೋ߯㡸৾⓸ዕߧ߮Ⲻ␼߫ᭉ߹ߦ╝〬៊㋨߯┤ 30 ৾⍁ዕ. ୡ㎮ߙࠋߪࠉ߰㡸N ࠒᝪ⍁ጟ߮᫖᜼㡸r ࠒఽ㋨ଁ߮ᄗᤐ߮ৼ᜼㡸ε ࠒ૔߮ఽ㋨ታ߫ᅟߙࠋᤐ 2. ߮ୡ㎮߮↉ᅟ⓸ዕ߮ᗓᄓߨߙࠋߨ㡸Ⲻ␼ㄤ߯ O(rN log2 ε. −1. ㋕ߏߪߣߟ㡵㡺. ៎ၮ: Ⲻ␼߮ᕞ㋨߮㏻ߋࠉ߯㡸ច߫ᄗᤐߌୡ㎮ߧߍߟఽ㋨߫ᅟߗߦ߯㡸ত߈߰ᝪ⍁ጟ߮྽. ᄗ 㕰 ߫ ⁌ ߄ ߟ N ᫖ ྽ 㑦 ጟ F (x) ߮ ࠼ࠢࡎ ࠲ࠢࡐ ᆛ ㋡ ৉ ᜼ fk 㡸k=0, 1, . . ., N ߯ √ fk =rk / k + 1㡸k=0, 1, . . ., N −1㡸fN =10−12 ߨࢬ߈ߟ㡺७ߗ rk ≡ cos{(k + 1)2 } ߨߗߟ.. 㑦ጟ߮⏵ೄࠒ⁌߄ࠋࣵୡᯜ㡸த◄ᯜ㡴࠶ࠦ࡮ࡃᯜ㡵㡸ࡆࡠࡷࡃ࡮ᯜߪߩ߮ಟ᎖߂ߟࠊ߮ᕞ㋨. ߓ߮ত㒖ߧ߯ᒊ๵ℽ߫ᡊ㗀᫖߮㑦߮৉᜼㡴ߠߑ㡵ࠒ᧤ࠁߦᅮߕ߄ਓ17) ߫ߗߦ߄ࠋ㡺᫖᜼ N. ߌ O(N ) ߮␼ᯜࠒ⁌߄ࠋᝪߌ㡸ఽ㋨ࠒࣵୡதߙࠋᭆ߫ O(N 2 ) ߮Ⲻ␼ㄤࠒᎨⱲߨߙࠋ࠴࠿ࡦ. ߌ 100㡸300㡸1000㡸3000 ߮ߝࠌߞࠌ߫ߤ߄ߦ㡸྽㑦ጟ F (x) ߮ࠫࡤࡐࠒ੘ 6㡸੘ 7㡸੘ 8㡸. ࡛ᯜ߫ᭉ߹ࠋߨ߯ࠋߋ߫❝὚ℽߧ߂ࠋ㡺. ੘ 9 ߫ᙀߒࠋ㡺. ) ߫ߪࠋ㡺. 4.1 ϬϷОГៀΤ೺⟣Ρ⻖΍Μ. 5.1 ϬϷОГ‫ݐ‬ψդΙΜׁᆳΏρଗࢮΤ೺ㅔֆ. • ࠴࠿ࡦ࡛୭ࠒⲺ␼ߙࠋ㍻߫㡸ᴘ␼߫ࠈࠊᰭ௫ᅮ᜼ᷲ᜼߮ᗓ᜼んߌ᫾ⱻట᜼߮⑚๴ࠒ⺉߈. ఽ㋨ [−1, 1] ଁ߮ F (x) ߮ᄗᤐ߮ৼ᜼ࠒ࠴࠿ࡦ࡛߮ᝪᯜ߫ࠈࠊᮀࠁߟ㡺⏵ೄྰట᜼ V (x). ߟߟࠁ߫⁄ߘࠋᡏ௖᜼რ߮᰸࿐ࠄࠝ࡮࠻ࡷࡐࡨࡷ␎ࠒ๥こߙࠋߟࠁ㡸஢ॿ߮྽㑦ጟࠒⲺ. ࠒఽ㋨߮ࢸ⏗ x = −1 ߨ x = 1 ߧߝࠌߞࠌᮀࠁߦ V (−1) − V (1) ߫ࠈࠊఽ㋨ [−1, 1] ଁ߮. ␼ߗߟࠉ㡴ߝࠌߌ㎸྽㑦ጟߧߪߑࠌ߰㡵ߝ߮৉᜼߮╺ᅟਓ߮ᡊ࿆ਓࠒᮀࠁߦ㡸ࣇࠁⴭቨ. ᤐ߮㡴ㄢⰦࠒ↏߄ߟ㡵ৼ᜼ߨߙࠋ㡺ᄗ㕰╡ᢲࠒ߾ߨࠁߟ㡴➱ 1㡵ಜ߳ࠫࡤࡐ㡴੘ 4㡵ߋࠉ㡸 ީ࠴࠿ࡦ࡛୭߮ংᔴުಜ߳㡸ច߫ᮀࠁߟ࠴࠿ࡦ࡛୭ࠒ୵⁌ߗߟީᄗᤐ߮ৼ᜼߮␼୘ު߮ߩߡ. ࠒߪࠋ߹ߏᅭ૭ߗߪ߄ࠈ߆߫ߙࠋߟࠁ߫ߝ߮ਓ߫ࠂߣߨࠂ⿏߄ީ༒᜼ (radix)ު߮ታ߮. ࠉࠂ㡸╝〬៊㋨߯྽㑦ጟ߮᫖᜼ N ߮ 2 ࣚ߫߻߼ᭉতߙࠋߓߨߌ≷ⴜߧߍࠋ㡺. ਓ㡴2 〖⯍ᾝ߮ᰭ௫ᅮ᜼ᷲ᜼߮ީ༒᜼ު߯ 2 ߧ߂ࠋ㡵ࠒ⁌߄ߦ྽㑦ጟ߮৉᜼ࠒதߣߦⱻ. ߕࠉ߫㡸࠴࠿ࡦ࡛ࣵୡᯜ߫ࠈࠊ 1) F (x) ߮ [−1, 1] ଁ߮ᄗᤐࠒౕᤐ߫ୡ㎮ߙࠋఽ㋨ࠒ૯ߦ. ᤒటߗߦ߄ࠋ㡺ߓ߮㡴᫾᜼߫ࠈࠋ㡵ⱻᤒటࠒ௃߈ߦࠂ㡸࠴࠿ࡦ࡛୭߮⏵ೄୱᄓ߯ྰటߗ. 3. c 2009 Information Processing Society of Japan .

(4) Vol.2009-HPC-122 No.4 2009/10/9. ᑔ༲େᾤძॗ∩⎇༲೸ IPSJ SIG Technical Report. ᮀࠁࠋ߾ߧ߮Ⲻ␼㡸ಜ߳ 2) F (x) ߮ [−1, 1] ଁ߮ᄗᤐࠒఽ㋨ኚ 10−8 ळࢩ߾ߧᮀࠁࠋⲺ␼㡸. ᫖᜼ N. ߮ࢸᝪࠒ⮷ߣߟ㡺╡ᢲ߮᜼ਓ㡴➱ 2㡵ߋࠉ㡸྽㑦ጟ߮᫖᜼ࠒ N 㡸ఽ㋨ଁ߮ᄗᤐ߮ৼ᜼ࠒ r ߨ ߗߦ㡸ఽ㋨ଁ߮ᄗᤐ૯んࠒఽ㋨ኚ 10−8 ळࢩ߾ߧᮀࠁࠋ╝〬៊㋨ࠒ ≈ c1 r N 2 ߨߙࠋߨߍ㡸. 100 300 1000 3000 10000. ৉᜼ c1 ߯ ≈ 1 × 10−7 (sec) ߨߪߣߟ㡺 10. ➱ 2 ఽ㋨ [−1, 1] ଁ߮ᄗᤐ߮ୡ㎮ఽ㋨߮ᨖᔴ㡸ಜ߳⓸ዕ 10−8 ߧ߮ᮀⲥ㡺 ࠴࠿ࡦ࡛୭߮⁄ᔴ ␼୘ߕࠌߟ ᄗᤐ߮ୡ㎮ఽ㋨߮ᨖᔴ ⓸ዕ 10−8 ߧ߮ᮀⲥ ╝〬៊㋨ (sec) ᄗᤐ߮ৼ᜼ ╝〬៊㋨ (sec) ╝〬៊㋨ (sec). 5.9E-5 4.2E-4 4.3E-3 4.2E-2 4.8E-1. 34 86 184 388 1355. 2.6E-3 5.2E-2 1.4E-0 2.7E+1 1.0E+3. 3.8E-2 8.0E-1 1.7E+1 3.1E+2 1.0E+4. make Sturm seq make root count ELAPSE TIME(SECOND). 1. ಜ߳ࠫࡤࡐ㡴੘ 5㡵ߋࠉ㡸࠴࠿ࡦ࡛୭ࠒ⁄ᔴߗߪߌࠉީᄗᤐ߮ৼ᜼߮␼୘ުࠒߙࠋ༴ೋ߮╝ 〬៊㋨ߌ㡸ࠄ߯ࠊ྽㑦ጟ߮᫖᜼ N ߮ 2 ࣚ߫߻߼ᭉতߙࠋߓߨࠒ≷ⴜߧߍࠋ㡺. 0.1. ߕࠉ߫࠴࠿ࡦ࡛ࣵୡᯜ߫ࠈࠊ 1) F (x) ߮ [−1, 1] ଁ߮ᄗᤐࠒౕᤐ߫ୡ㎮ߙࠋఽ㋨ࠒ૯ߦᮀ ࠁࠋ߾ߧ߮Ⲻ␼㡸ಜ߳ 2) F (x) ߮ [−1, 1] ଁ߮ᄗᤐࠒఽ㋨ኚ 10−8 ळࢩ߾ߧᮀࠁࠋⲺ␼㡸߮. 0.01. ࢸᝪࠒ⮷ߣߟ㡺╡ᢲ߮᜼ਓ㡴➱ 4㡵ߋࠉ㡸྽㑦ጟ߮᫖᜼ࠒ N 㡸ఽ㋨ଁ߮ᄗᤐ߮ৼ᜼ࠒ r ߨ ߗߦ㡸ఽ㋨ଁ߮ᄗᤐ૯んࠒఽ㋨ኚ 10−8 ळࢩ߾ߧᮀࠁࠋ╝〬៊㋨ࠒ ≈ c2 r N 2 ߨߙࠋߨߍ㡸. 0.001. ৉᜼ c2 ߯ ≈ 3 × 10−7 (sec) ߨߪߣߟ㡺. 0.0001. ࠴࠿ࡦ࡛୭ࠒয়ᗏߛߚ߫ᭆ๥ᎨⱲ߫Ꮈߘߦ⁄ᔴߙࠋߓ߮༴ೋ߯㡸ⳇᓻㄤߌ O(N ) ߨߪࠊ㡸 য়ᗏߙࠋ༴ೋ߮ O(N 2 ) ߫ᭉ߹ߦ࿆ኚ߫᲍ࠋ߮ߧ㡸࿆ߍߪ᫖᜼߮ᝪ⍁ጟ߮ᄗᤐⲺ␼ߌ㡴Ⲻ␼. 1e-05 100 ੘4. 1000 10000 DEGREE OF POLYNOMIAL. 100000. ៊㋨ࠒߋߑࠌ߰㡵ಽ❝ߨߪࠋ߻ߋ㡸᫖᜼߮ᅮߕ߄༴ೋ߫߯ᎨⱲߪⳇᓻㄤ߮૯ॹߌࠨ࡞࠾࠲ࡠ ߫ಠ߾ࠊࠄߙߏߪࠋ㡺. ࠴࠿ࡦ࡛୭߮⁄ᔴߨᄗᤐ߮ৼ᜼␼୘߮╝〬៊㋨㡴ࢸᅟ᜼ࡒࡨ࠾ࡃ㡵㡺. ᾝປ߮ᄗ⯿߯㡸ᱵߕુ૙໗ౕ߮┲ߪଇ኎େᾤࠒ⁌߄ߦࣵୡᯜࠒ⮷ߪߣߦ߄ࠋ߮ߧ㡸ఽ㋨߮ ࣵୡதࠒ⮷ߪ߆ߟ߳߫࠴࠿ࡦ࡛୭ࠒ⁄ᔴߗߪߌࠉ⏵ೄྰట᜼ࠒⲺ␼ߙࠋ㡺ߝ߮ߟࠁ㡸࠴࠿ࡦ ➱1 ᫖᜼ N. 100 300 1000 3000 10000 30000. ࡛୭૯ॹࠒ૙߫࢟ዕⲺ␼ߗߦয়ᗏߗ㡸ᎂ߯ߝࠌࠒচ߄░ߑࠋᝪᯜ߫ᭉ߹ࠋߨ㡸ᴘ␼๥᜼ࠂⳇ ࠴࠿ࡦ࡛୭߮⁄ᔴߨᄗᤐ߮ৼ᜼␼୘߮╝〬៊㋨㡺 ࠴࠿ࡦ࡛୭߮⁄ᔴ ᄗᤐ߮ৼ᜼␼୘ ␼୘ߕࠌߟ ╝〬៊㋨ (sec) ╝〬៊㋨ (sec) ᄗᤐ߮ৼ᜼. 5.9E-5 4.2E-4 4.3E-3 4.2E-2 4.8E-1 4.7E-0. 5.1E-5 4.4E-4 4.7E-3 4.3E-2 4.8E-1 4.4E-0. ᓻࠒಗḸߙࠋ๥᜼ࠂࢸᝪߨࠂཫ߈ࠋߟࠁ㡸Ⲻ␼߮╝〬៊㋨ߌ┤ 3 ৾⍁ዕ߫㋕ߏߪߣߦ߄ࠋ㡺 ➱ 3 ᄗᤐ߮ৼ᜼␼୘߮╝〬៊㋨㡴࠴࠿ࡦ࡛୭ࠒᭆ๥⁄ᔴ㡵㡺 ᫖᜼ N ᄗᤐ߮ৼ᜼␼୘ ␼୘ߕࠌߟ ╝〬៊㋨ (sec) ᄗᤐ߮ৼ᜼. 34 86 184 388 1355 6145. 100 300 1000 3000 10000 30000 100000. 5.2 ϬϷОГ‫ݐ‬ψׁᆳΑΐΡᜪੈᰨᄘΏρଗࢮΤ೺ㅔֆ. 9.0E-5 5.9E-4 6.0E-3 5.4E-2 6.2E-1 5.8E-0 6.7E+1. 34 86 184 388 1355 6145 22952. ࠴࠿ࡦ࡛߮ᝪᯜ߫ࠈࠊఽ㋨ [−1, 1] ଁ߮ F (x) ߮ᄗᤐ߮ৼ᜼ࠒᮀࠁࠋᄗ㕰╡ᢲ߮᜼ਓ㡴➱ 3㡵. 4. c 2009 Information Processing Society of Japan .

(5) Vol.2009-HPC-122 No.4 2009/10/9. ᑔ༲େᾤძॗ∩⎇༲೸ IPSJ SIG Technical Report. • 〄ኔ߮ఽ㋨߮ࣵୡதᯜࠒ྽ୡதᯜ߫ߙࠌ߰Ꮻ❝ࠒީ⢑኶ު㗀ࠁࠋߓߨߌߧߍࠈ߆㡺ᮀࠁ. 100 Root Counting. ߟ߄ᤐߌ࢟᨟ࡤ࡮࠻࡛߫ୡቶߗߦ߄ࠋߨशᄓߙࠌ߰㡸ୡத߮ 1 ᬳ㍱ߧఽ㋨ࠒ s ␎ୡߙࠋ. ELAPSE TIME(SECOND). 10. ༴ೋ㡸ఽ㋨◹ᅮߧᎊࠋᑔ༲ㄤ߯ log2 (s) ࡎ࠾ࡃߧ߂ࠋ㡺ఽ㋨ࠒ s ୡதࠒߙࠋߟࠁ߫߯㡸 ఽ㋨߮ࢿ߫ᝥߟߪ s−1 ৼ߮ୡᷲ߮Ⲻ␼ߌᎨⱲߧ㡸ߝࠌࠒ p ৼ߮ࡒࡨ࠶࠰ߧỽ⎻߫⳱সߧ. 1. ߍࠋߨ㡸1 ৼ߮ୡᷲࠒ 1 ࡒࡨ࠶࠰ߧⲺ␼ߙࠋ༴ೋ߮ (s−1)/p ৾߮Ⲻ␼៊㋨ߌᘭߋࠋ㡺. 0.1. ࠈߣߦ㡸ࡒࡨ࠶࠰᜼ࠒ p ৼ߫ߗߟ༴ೋ߮ީᏫ❝೔ࢨᭉުE(p) ߯ log2 (s)/(s−1)/p ߧ㡸. p ࠒᮡࠁߟߨߍ߫ s=p+1 ߧᡊ࿆ࠒߨࠊ㡸E(p) = log2 (p+1) ߨߪࠋ㡺ཫ௃߯ࡒࡨ࠶࠰᜼. 0.01. p ߫ᅟߗߦᅟ᜼ℽߧ㡸E(1) = 1.0㡸E(2) = 1.6㡸E(3) = 2.0㡸E(4) = 2.3㡸E(5) = 2.6㡸. 0.001. E(6) = 2.8㡸E(7) = 3.0㡸E(8) = 3.2 ߪߩߨߪࠋ㡺࠴࠿ࡦ࡛୭ࠒᭆ๥⁄ᔴߙࠋ༴ೋ߫ ߯㡸ߝ߮⁄ᔴߙࠋᕞ㋨ࠒ s−1 ৼ߮ୡᷲ߫ᝫߑࠋ⏵ೄྰట᜼߮⳱স߮㋨ߧ૶ᡏߧߍࠋ߮. 0.0001. ߧ㡸ࡒࡨ࠶࠾࠰᜼ߌ p = 1 ߮༴ೋߧ߂ߣߦࠂ㡸2 ࠈࠊ࿆ߍ߄ୡத᜼ s ࠒᘱࠋߓߨߧ㡸௖. 1e-05 100. 1000. 10000. ὚߮᜚ඤߌᡞ፼ߧߍࠋ㡺. 100000. DEGREE OF POLYNOMIAL. • ᾝປ㡸ᄗᤐ߮ୡ㎮ౕ߫߯┲ߪఽ㋨߮ଇ኎ࣵୡத߫ࠈࠋ⟦Ḟߪᱵߕુ૙ᘲ┿ᯜࠒ⁌߄ߦ߄. ੘ 5 ᄗᤐ߮ৼ᜼␼୘߮╝〬៊㋨㡴࠴࠿ࡦ࡛୭ࠒᭆ๥⁄ᔴ㡵㡴ࢸᅟ᜼ࡒࡨ࠾ࡃ㡵㡺. ࠋߌ㡸ߝࠌࠒ᜚⡁ߗߦᡊ୯߮ఽ㋨߫ೡ߾ࠌࠋᤐ߮ৼ᜼ߌ྽߄ߨߍ߫߯ኚુ૙ᘲ┿ࠒ⁌߄ ࠋࠈ߆߫ ␼ᯜߨࡂࡷ࠺ᨖ〉ࠒྰᠿߙࠌ߰㡸࢟ዕ߫߾ߨࠁߦ⏵ೄྰట᜼ V (x) ࠒⲺ␼ߙ ࠋୡᷲ x ߮ৼ᜼ࠒཫࠄߛࠋ߮ߧ㡸Ⲻ␼௖὚ࠒ㗀ࠁࠉࠌࠋߧ߂ࠍ߆㡺㡴ⳇᓻㄤࠒ⑗┤ߙࠋ. ➱4. ఽ㋨ [−1, 1] ଁ߮ᄗᤐ߮ୡ㎮ఽ㋨߮ᨖᔴ㡸ಜ߳⓸ዕ 10−8 ߧ߮ᮀⲥ㡴࠴࠿ࡦ࡛୭ࠒᭆ๥⁄ᔴ㡵㡺 ᫖᜼ N ␼୘ߕࠌߟ ᄗᤐ߮ୡ㎮ఽ㋨߮ᨖᔴ ⓸ዕ 10−8 ߧ߮૯ᮀⲥ ᄗᤐ߮ৼ᜼ ╝〬៊㋨ (sec) ╝〬៊㋨ (sec). 100 300 1000 3000 10000. 34 86 184 388 1355. 8.1E-3 1.4E-1 3.5E-0 6.9E+1 2.7E+3. ߟࠁ࠴࠿ࡦ࡛୭ࠒয়ᗏߛߚ߫㡸ୡᷲ߮╗ x1 , x2 , . . . , xp ߌᗓᄓߕࠌߟߨߍ߫㑧᫖࠴࠿ࡦ ࡛୭ࠒ⁄ᔴߗߪߌࠉߝࠌ߫ঐߛߦ⏵ೄྰట᜼ V (x1 ), V (x2 ), . . . , V (xp ) ࠒ࢟ዕ߫߾ߨࠁ. 1.2E-1 2.2E-0 4.5E+1 7.8E+2 2.7E+4. ߦᮀࠁࠋ༴ೋ߯Ệ߫ߝ߆ߧ߂ࠋ㡵㡺. ࡺ. ⊮. ጬ. ᬈ. 1) ᡽ࢨ ጧ: ީఽ㋨ଁߧ߮ↇई྽㑦ጟᆛ㋡߫ࠈࠋᡏᾤ㋲᜼Ⰾ㋨ު, ᑔ༲େᾤძॗ∩⎇༲೸, 2006-HPC-108 (2006), pp.55-60. 2) ᡽ࢨ ጧ: ީ᜼ਓऱ᜼ᝪ⍁ጟ߮ࡐࠞࡦ࠺ᅟⲜటᯜ߫ࠈࠋⲥᯜު , ऍ゜࿆ძ᜼ᾤⲥᢨ∩⎇ ᕕⶂ⎇㈕, No.1652 (2009), pp.134-145. 3) Hiroshi Murakami: ”Application of Filter Diagonalization Method to Numerical Solution of Algebraic Equations”, proceedings of the 3rd International Workshop on Symbolic-Numeric Computation (SNC2009), Kyoto, Japan (2009), pp.95-104. 4) 㗀ᡣ⸗ᯈ: ީऱ᜼ძⶂ⚗ (᜚ⲵᝥấ)ު, ⏻ 3 ⏊:‘࠴࠿ࡦ࡛߮උ㒖, ᤐ߮Ⲻ␼’, ૶⎻୘ấ (1965). 5) Abramowitz,M. and Stegun,I.A. Eds.: Handbook of Mathematical Functions: with Formulas, Graphs, and Mathematical Tables, New York, Dover (1972). 6) Bini,D.A., Daddi,F. and Gemignani,L.: ”On the Shifted QR Iteration Applied to. 6. ӿསΤ⤜ぺ㑤ዾইΤࢠ⍁࿏ • झ๥߮ᄗ㕰ߧ߯૯ߦ 1CPU ଁ߮ 1 ࠮ࠝߧ⮷ߪߣߦߊࠊ㡸ࢻ୭ట߯૯ߏߗߦ߄ߪ߄㡺᫖᜼ ߮㗀߄༴ೋࠄᮀࠁࠋᤐ߮ৼ᜼ߌ྽߄༴ೋ߫߯㡸MPI ࠄ OpenMP ߪߩࠒ⁌߄ߟࢻ୭େᾤࠒ ⮷߆ߓߨߧ㡸࠴࠿ࡦ࡛୭⁄ᔴ߮྽㑦ጟ஢ॿ߮Ⲻ␼ࠒ㗀〈టߙࠋߓߨߌಽ❝ߧ߂ࠋ㡺࠼ࠢ ࡎ࠲ࠢࡐ৉᜼ߋࠉࢬ߈ࠉࠌߟୡᷲ߫ᅟߙࠋ྽㑦ጟ߮ਓࠒⲺ␼ߙࠋ␰ᕕ߯㡸Clenshaw ߮ ␼ᯜ߮߾߾ߧ߯ᴭటጟ߫༒ߥߏ⿻᫖େᾤ߮ߟࠁ㡸᫖᜼ᝪ೔ࠒୡதߗߟࢻ୭ట߯୘ᢌߪ߄㡺. 5. c 2009 Information Processing Society of Japan .

(6) Vol.2009-HPC-122 No.4 2009/10/9. ᑔ༲େᾤძॗ∩⎇༲೸ IPSJ SIG Technical Report. Companion Matrices”, ETNA(Electronic Transaction on Numerical Analysis), v18 (2004), pp.137–152. 7) Boyd,J. P.: ”Computing Zeros on a Real Interval Through Chebyshev Expansion and Polynomial Rootfinding”, SIAM J. Numer. Anal., v40, no.5 (2002), pp.1666– 1682. 8) Boyd, J.P. and Gally, D.H.: ”Numerical Experiments on the Accuracy of the Chebyshev-Frobenius Companion Matrix Method for Finding the Zeros of a Truncated Series of Chebyshev Polynomials”, J. Comput. and Appl. Math., v205, no.1 (2007), p.281-295. 9) Boyd,J. E.: ”Computing Real Roots of a Polynomial in Chebyshev Series form Through Subdivision”, Applied Numerical Math., v56, no.8 (2006), pp.1077–1091. 10) Day,D. and Romero,L.: ”Roots of Polynomials Expressed in Terms of Orthogonal Polynomials”, SIAM J. Numer. Anal., v43, no.5 (2005), pp.1969–1987. 11) Gautschi, W.: ”The Condition of Orthogonal Polynomials”, Math. Comp., v26, no.120 (1972), pp.923–924. 12) Gautschi, W.: ”On the Condition of Algebraic Equations”, Numer. Math., v21 (1973), pp.405–424. 13) Gautschi,W.: ”The Condition of Polynomials in Power Form”, Math. Comp., v33, no.145 (1979), pp.343–352. 14) Golub,G.H. and Van Loan,C.F.: Matrix Computations, 3rd Ed., The Johns Hopkins University Press, Baltimore, Maryland (1983). 15) Hasegawa, T., Torii, T. and Sugiura, H.: ”An algorithm based on the FFT for a generalized Chebyshev interpolations”, Math. Comp., v54 (1990), pp.195–210. 16) Jia,Z. and Stewart,G.W.: ”An Analysis of the Rayleigh-Ritz Method for Approximating Eigenspaces”, Math. Comp., v70, no.234(2001), pp.637–647. 17) G.F.J´ onsson and S. Vavasis, J´ onsson,G.F. and Vavasis,S.: ”Solving polynomials with small leading coefficients”, SIAM J. Matrix Anal. Appl., v26 (2004), pp.400– 414. 18) Sherlock,B.G. and Monro,D.M.: ”Algorithm 749:fast discrete cosine transform”, ACM Trans. Math. Soft., v21, no.4 (1995), pp.372–378. 19) Szeg¨ o,G.: Orthogonal Polynomials, 4th Ed., AMS Colloquium Publications XXIII, New York (1975).. Random Polynomial of Degree 100. 6. Value of Polynomial. 4 2 0 -2 -4 -6 -1. -0.5. 0. 0.5. 1. x ੘ 6 ত㒖߮ࡤ࡮࠻࡛྽㑦ጟ㡴N = 100㡵㡺ఽ㋨ [−1, 1] ߫ᤐ߯ 34 ৼ㡺. Random Polynomial of Degree 300. 6. Value of Polynomial. 4 2 0 -2 -4 -6 -1. -0.5. 0. 0.5. 1. x ੘ 7 ত㒖߮ࡤ࡮࠻࡛྽㑦ጟ㡴N = 300㡵㡺ఽ㋨ [−1, 1] ߫ᤐ߯ 86 ৼ㡺. 6. c 2009 Information Processing Society of Japan .

(7) Vol.2009-HPC-122 No.4 2009/10/9. ᑔ༲େᾤძॗ∩⎇༲೸ IPSJ SIG Technical Report. Random Polynomial of Degree 1000. 6. Value of Polynomial. 4 2 0 -2 -4 -6 -1. -0.5. 0. 0.5. 1. x ੘ 8 ত㒖߮ࡤ࡮࠻࡛྽㑦ጟ㡴N = 1000㡵㡺ఽ㋨ [−1, 1] ߫ᤐ߯ 184 ৼ㡺. Random Polynomial of Degree 3000. 6. Value of Polynomial. 4 2 0 -2 -4 -6 -1. -0.5. 0. 0.5. 1. x ੘ 9 ত㒖߮ࡤ࡮࠻࡛྽㑦ጟ㡴N = 3000㡵㡺ఽ㋨ [−1, 1] ߫ᤐ߯ 388 ৼ㡺. 7. c 2009 Information Processing Society of Japan .

(8)