第59回プログラミング・シンポジウム 2018.1.19-21

ภඍ෼ํఔࣜͷղͷ‫ػࢉܭ‬ԉ༻ଘࡏূ໌๏ͷͨΊͷ
C++Λ༻͍ͨਫ਼౓อূ෇͖਺஋‫ࢉܭ‬ϥΠϒϥϦͷ
ߏஙؔࠜ ߊଠ1,a)֓ཁɿ਺஋‫ͱࢉܭ‬͸ίϯϐϡʔλΛ࢖ͬͯ਺ֶతʹ‫ه‬ड़͞ΕͨखͰ͸ղ͚ͳ͍໰୊Λۙࣅతʹղ͘ख๏Ͱ͋Γɼ‫ݱ‬୅ͷՊֶʹ͸͔ܽͤͳ͍ٕज़Ͱ͋Δɽ͔͠͠ɼۙࣅతʹ͔͠ղ͕‫·ٻ‬Βͳ͍ͨΊɼਖ਼͍͠ղʹ͍͔ۙͲ͏͔͑͞Θ͔Βͳ͍ɽਫ਼౓อূ෇͖਺஋‫ͱࢉܭ‬͸਺஋‫ࢉܭ‬Ͱൃੜ͢Δશͯͷ‫ࠩޡ‬Λ೺Ѳ͠ɼ਺ֶతʹਖ਼͍݁͠ՌΛ਺஋‫ʹࢉܭ‬ΑͬͯಘΔ͜ͱΛ͍͏ɽ
ଈͪɼIEEE 754 Ͱ‫֨ن‬Խ͞Εͨුಈখ਺఺਺ͷ‫ൃͰࢉܭ‬ੜ͢Δ‫ؙ‬Ί‫͔ࠩޡ‬Β Newton ๏ͳͲͷ൓෮ղ๏ͷଧ੾Γ‫ࠩޡ‬ɼ͞Βʹ͸༗‫ݶ‬ཁૉ๏ͳͲͷภඍ෼ํఔࣜͷۙࣅղΛ‫ٻ‬ΊΔࡍʹൃੜ͢Δ཭ࢄԽ‫Ͱ·ࠩޡ‬શͯͷ‫ࠩޡ‬Λ೺Ѳͯ͠‫͢ࢉܭ‬Δख๏Ͱ͋Δɽ͞Βʹɼ਺ֶతʹղ͕Θ͔͍ͬͯͳ͍໰୊ʹదԠ͢Ε͹ɼ‫ػࢉܭ‬Λ༻͍ͨ਺ֶͷূ໌ʹ΋ͳΔɽ͔͠͠ɼਫ਼౓อূ
෇͖਺஋‫ࢉܭ‬͸ුಈখ਺఺਺ͷ‫ؙ‬ΊϞʔυͷ੍‫ޚ‬ͷϓϩάϥϜ͔Β਺ֶͷ஌ࣝ·ͰඞཁʹͳΔͨΊ‫ʹܰؾ‬Ϣʔβʔ͸ར༻͠ʹ͍͘ঢ়‫͋ʹگ‬Δɽͦ͜ͰຊߨԋͰ͸ɼ‫ػࢉܭ‬Λ༻͍ͨภඍ
෼ํఔࣜͷղͷଘࡏূ໌Λ࠷ऴ໨తͱͨ͠਺஋ઢ‫ܗ‬୅਺ϥΠϒϥϦͷߏங๏ͱஶऀ͕࡞੒ͨ͠ VCP Library ʹ͍ͭͯ঺հ͢ΔɽΩʔϫʔυɿਫ਼౓อূ෇͖਺஋‫ࢉܭ‬ɼ‫ػࢉܭ‬ԉ༻ଘࡏূ໌๏ɼC++11ɼVCP Library੾Γࣺͯ΍੾Γ্͛ʹΑͬͯۙࣅ͢Δ͜ͱͰුಈ

1. ͸͡Ίʹ

খ਺఺਺ʹ͢Δɽྫ͑͹ʮ1ʯ΋ʮ3ʯ΋ഒਫ਼౓ු਺஋‫ͱࢉܭ‬͸ίϯϐϡʔλΛ࢖ͬͯɼ਺ֶతʹಈখ਺఺਺Ͱ‫ه‬ड़Մೳ͕ͩɼʮ1/3ʯͷ݁Ռ͸ഒਫ਼‫ه‬ड़͞Εͨ໰୊Λղ͘ख๏Ͱ͋Γɼ‫ݱ‬୅ͷՊֶʹ౓ුಈখ਺఺਺Ͱ‫ه‬ड़͢Δ͜ͱ͸Ͱ͖ͳ͍ɽ͜ͷ͸͔ܽͤͳ͍ٕज़Ͱ͋ΔɽҰൠతʹར༻͢ΔίϯΑ͏ʹුಈখ਺఺਺ͷԋࢉʹΑͬͯൃੜ͢Δ‫ࠩޡ‬ϐϡʔλ͸࣮਺Λ IEEE 754 Standard [1] ͰఆΊΛ‫ؙ‬Ί‫͏͍ͱࠩޡ‬ɽͦͷͨΊɼුಈখ਺఺਺ͷԋΒΕͨුಈখ਺఺਺ʹۙࣅͯ͠ԋࢉΛߦ͏ɽྫ͑

ࢉ͸ඇৗʹߴ଎Ͱ͋Δ൓໘ɼԋࢉΛ‫ͯܦ‬ಘΒΕͨ͹ɼ࣮਺ʮ1.2ʯ͸ IEEE 754 Standard ͰఆΊΒΕ݁Ռ͸‫ؙ‬Ί‫ࠩޡ‬Λ‫ؚ‬Ήۙࣅ஋ͱͳΔ.

͍ͯΔഒਫ਼౓ුಈখ਺఺਺Ͱ͸ਅͷ஋Ͱද͢͜ͱ

਺஋‫ࢉܭ‬Λߦ͏্Ͱ͸ɼ‫ؙ‬Ί‫ࠩޡ‬ͷଞʹ΋༷ʑ͕ग़དྷͳ͍ͨΊۙࣅ͞ΕΔɽ·ͨɼුಈখ਺఺਺

ͳ‫͕͋ࠩޡ‬Δɽྫ͑͹ɼίϯϐϡʔλΛ༻͍ͯੵಉ࢜ͷԋࢉ݁Ռ΋ුಈখ਺఺਺Ͱදͤͳ͍৔߹ɼ

෼஋Λ‫ٻ‬Ί͍ͨ৔߹ʹར༻͢Δ਺஋ੵ෼๏͸

 b
1
a)

౦༸େֶ৘ใ࿈‫ֶܞ‬Պsekine123@iniad.orga153

f (x)dx ≈N
i=1

f (xi )wi

第59回プログラミング・シンポジウム 2018.1.19-21ͱ΋‫ݺ‬͹ΕΔɽͷΑ͏ʹੵ෼Λ༗‫ݶ‬࿨ʹۙࣅͯ͠‫ࢉܭ‬Λߦ͏ɽ·ͨɼඇઢ‫ํܗ‬ఔࣜ f (x) = 0 ͷղΛ‫ٻ‬ΊΔࡍʹྑ͔͘͠͠ɼภඍ෼ํఔࣜͷղʹର͢Δ‫ػࢉܭ‬ԉ༻ଘࡏূ໌๏͸༗‫ݩ࣍ݶ‬໰୊ʹର͢Δਫ਼౓อূ෇͖ར༻͞ΕΔ Newton ๏਺஋‫ࢉܭ‬๏ͷ݁ूͰ͋ΓɼϓϩάϥϜ͕ඇৗʹෳ

xi+1 = xi − f  [xi ]−1 f (xi )ࡶʹͳͬͯ͠·͏ɽͦͷͨΊʹɼਫ਼౓อূ෇͖਺

͸ʮ࣮਺‫ࢉܭ‬ʯΛʮແ‫ݶ‬ճʯ‫܁‬Γฦ͢͜ͱʹΑͬ஋‫ࢉܭ‬ϥΠϒϥϦΛར༻͢Δ͜ͱͰ޷·͍͠ɽ‫ݱ‬ͯਅͷղ͕ಘΒΕΔɽ͔͠͠ɼίϯϐϡʔλͰ͸ঢ়͋Δ༗໊ͳਫ਼౓อূ෇͖਺஋‫ࢉܭ‬ϥΠϒϥϦ͸

ʮුಈখ਺఺ԋࢉʯΛʮ༗‫ݶ‬ճʯ‫܁‬Γฦͨ݁͠Ռ͠

ҎԼͷ 2 ͭͰ͋Δ:

S.M. Rump, INTLAB, ‫ޠݴ‬: MATLAB [2]͔ಘΒΕͳ͍ͨΊɼਅͷղ͕ಘΒΕ͍ͯΔΘ͚Ͱ਺஋ઢ‫ܗ‬୅਺ʹର͢Δਫ਼౓อূ෇͖਺஋‫ܭ‬͸ͳ͍ɽ͜ͷΑ͏ʹίϯϐϡʔλͰಘΒΕͨ݁Ռ͸ඞͣࢉ๏ͷઐ໳ՈͰ͋Δ S.M. Rump ࢯ͕࡞੒͠

͠΋ਖ਼͍͠Θ͚Ͱ͸ͳ͍ɽͦͷͨΊʹۙࣅղ͕Ͳ

ͨϥΠϒϥϦɽMATLAB ʹ࣮૷͞Ε͍ͯΔ

ͷఔ౓ਖ਼͍݁͠ՌΛಘ͍ͯΔͷ͔͔֬ΊΔखஈ͕

BLAS ͱ LAPACK Λར༻ͨ͠ߴ଎ͳߦྻɼ

ඞཁͰ͋Γɼ͞Βʹਖ਼͠͞Λ͔֬Ίͨ݁Ռɼඞཁ

਺஋ઢ‫ܗ‬୅਺ʹؔΘΔਫ਼౓อূ෇͖਺஋‫ࢉܭ‬ʹԠͯۙ͡ࣅղͷվળ΋ඞཁͱͳΔɽ‫·ؚ͕ࠩޡ‬͕‫ྗڧ‬ɽദ໦խӳ, kv Library, ‫ޠݴ‬: C++ [3]Εͨۙࣅղ͕Ͳͷఔ౓ਖ਼͍݁͠ՌΛಘ͍ͯΔ͔֬ৗඍ͔ΊΔखஈͱͯ͠ਫ਼౓อূ෇͖਺஋‫ࢉܭ‬๏͕͋Δɽ

෼ํఔࣜͷղʹର͢Δਫ਼౓อূ෇͖਺஋‫ࢉܭ‬ਫ਼౓อূ෇͖਺஋‫ͱࢉܭ‬͸ɼ࿈ཱҰ࣍ํఔࣜΛ͸๏͕ઐ໳ՈͰ͋Δദ໦խӳࢯ͕࡞੒ͨ͠ϥΠ͡Ίͱͨ͠‫ݻ‬༗஋໰୊ɼੵ෼ɼඍ෼ํఔࣜͳͲͷϒϥϦɽৗඍ෼ํఔࣜͷਫ਼౓อূ෇͖਺஋‫ܭ‬ղ͖͍ͨ໰୊ͷਅͷղ x∗ ͱۙࣅղ x̂ ʹର͠ɼίϯࢉ๏͕࣮૷͞Ε͍ͯΔɽ·ͨɼDouble-DoubleϐϡʔλΛ༻͍ͯ਺ֶతʹ‫ࠩޡͳີݫ‬ͷ্քΛಘԋࢉ (ٙࣅ 4 ഒਫ਼౓ԋࢉ) ΍ MPFR Λ༻͍ͨΔख๏Ͱ͋Δɽߴਫ਼౓ͳεΧϥʔ‫ʹࢉܭ‬ର͢Δਫ਼౓อূ෇͖
਺஋‫ࢉܭ‬๏͕࣮૷͞Ε͍ͯΔɽ͞Βʹɼਫ਼౓อূ෇͖਺஋‫ࢉܭ‬๏͸ඇઢ‫ܗ‬ภඍ෼ํఔࣜͷ‫ڥ‬ք஋໰୊ͳͲʹ΋దԠ͞ΕΔɽඇઢͦͷ্Ͱɼภඍ෼ํఔࣜͷղʹର͢Δ‫ػࢉܭ‬ԉ‫ܗ‬ภඍ෼ํఔࣜ͸ແ‫ݩ࣍ݶ‬໰୊Ͱ͋Γίϯϐϡʔ༻ূ໌๏Ͱ͸ɼʮ਺஋ઢ‫ܗ‬୅਺ʹؔΘΔߴ଎ͳਫ਼౓

λͰ͸ͦͷ··‫͍ͳ͖Ͱࢉܭ‬ɽͦͷͨΊɼ༗‫ݶ‬ཁอূ෇͖਺஋‫ࢉܭ‬ʯͱʮߴਫ਼౓ͳεΧϥʔ‫ʹࢉܭ‬ରૉ๏ͳͲͷํ๏Λ༻͍ͯ཭ࢄԽ͠ɼ༗‫ݩ࣍ݶ‬໰୊

͢Δਫ਼౓อূ෇͖਺஋‫ࢉܭ‬๏ʯʹՃ͑ʮ਺஋ઢ‫ܗ‬ʹۙࣅ͔ͯ͠ΒίϯϐϡʔλͰ‫͢ࢉܭ‬Δɽ·ͨɼ୅਺ʹؔΘΔߴਫ਼౓ͳਫ਼౓อূ෇͖਺஋‫ࢉܭ‬ʯ͕ඇઢ‫ܗ‬ภඍ෼ํఔࣜͷਅͷղ΋ແ‫ͳʹݩ࣍ݶ‬ΓɼඞཁʹͳΔɽͦͷͨΊ‫ݱ‬ঢ়Ͱ͸ɼແ‫ݩ࣍ݶ‬Λѻ͏ਅͷղ͕ͦ΋ͦ΋ଘࡏ͢Δ͔ղੳతʹূ໌͞ΕͯͨΊͷ਺ֶͰ͋Δؔ਺ղੳͷ஌ࣝͷΈͳΒͣɼ༗͍ͳ͍໰୊΋ଟ͋͘Δɽਫ਼౓อূ෇͖਺஋‫Ͱࢉܭ‬‫ݩ࣍ݶ‬ͷ༷ʑͳਫ਼౓อূ෇͖਺஋‫Ͱ·ࢉܭ‬΋೺Ѳ͸ɼແ‫ݩ࣍ݶ‬໰୊͔Β༗‫ݩ࣍ݶ‬໰୊ʹ཭ࢄԽͨ͠

Ͱ͖Δ‫͔͠ऀڀݚ‬ภඍ෼ํఔࣜͷղʹର͢Δ‫ࢉܭ‬ࡍͷ཭ࢄԽ‫͚ͳ͑ߟͰ·ࠩޡ‬Ε͹ͳΒͳ͍ɽͦͷ‫ػ‬ԉ༻ূ໌๏ʹؔ͢ΔϓϩάϥϜΛߏங͢Δ͜ͱͨΊʹ༗‫ݶ‬ཁૉ๏ͳͲΛར༻ͯ͠཭ࢄԽ͠ɼίϯ͸೉͍͠ɽͦͷͨΊʹຊ࿦จͰ͸ภඍ෼ํఔࣜͷϐϡʔλͰಘΒΕͨۙࣅղʹՃ͑ؔ਺ղੳͷ஌ࣝղʹର͢Δ‫ػࢉܭ‬ԉ༻ূ໌๏ͰඞཁͱͳΔ਺஋ઢ

Λར༻͢Δ͜ͱͰɼ
ʮίϯϐϡʔλΛ༻͍ͯඇઢ‫ܗ‬‫ܗ‬୅਺ϥΠϒϥϦΛҎԼͷΑ͏ʹఆٛ͢Δ:

ภඍ෼ํఔࣜͷղͷଘࡏੑΛূ໌ʯͭͭ͠ɼʮແ‫ݶ‬ఆٛ 1 (Ԡ༻্Ͱඞཁͳ਺஋ઢ‫ܗ‬୅਺ϥΠϒϥϦ)࣍‫ݩ‬໰୊ͷਅͷղ u∗ ʯͱʮ༗‫ݩ࣍ݶ‬໰୊ͷۙࣅղ• ༷ʑͳ‫ࢉܭྻߦͰܕ‬ɼ࿈ཱҰ࣍ํఔࣜɼ‫ݻ‬༗஋໰୊Λѻ͑Δûʯʹର͠਺ֶతʹ‫ࠩޡͳີݫ‬ͷ্քΛ༩͑Δɽ͜• double ‫ܕ‬͸࠷దԽ͞Εͨ BLAS, LAPACK Λརͷ͜ͱ͔Βɼภඍ෼ํఔࣜͷղʹର͢Δਫ਼౓อূ෇͖਺஋‫ࢉܭ‬͸͠͹͠͹ʮ‫ػࢉܭ‬ԉ༻ଘࡏূ໌๏ʯ

154

༻͠ߴ଎ʹ࣮ߦͰ͖Δ

第59回プログラミング・シンポジウム 2018.1.19-21• ্‫ ه‬2 ͭʹରͯ͠ਫ਼౓อূ෇͖਺஋‫ࢉܭ‬΋ՄೳϝʔδͰ͸ɼԁप཰ π = 3.14158 · · · ͷΑ͏ͳ࣮਺• ͢΂ͯΛม਺ͷ‫ܕ‬ͷΈͷมߋͰ੾Γସ͕͑Մೳ

͸ด۠ؒΛ༻͍ͯ π ∈ [3.14, 3.15] ͷΑ͏ʹਅͷ஋ຊ࿦จͰ͸ɼఆٛ 1 Λຬͨ͢਺஋ઢ‫ܗ‬୅਺ϥΠϒΛแ‫ؚ͢‬Δ۠ؒ [3.14, 3.15] Λ࡞੒͢Δɽ·ͨԋࢉϥϦͷ࡞੒͢Δखஈͱͯ͠ɼPolicy-based design Λʹ͓͍ͯ΋ɼ1/3 ∈ [0.3333, 0.3334] ͷΑ͏ʹਅͷ༻͍ͯ࡞੒͢Δ. ·ͨɼԠ༻ͱͯ͠࡞੒ͨ͠ϥΠϒղΛแ‫ؚ͢‬Δด۠ؒΛ࡞੒͢Δɽ͜ͷΑ͏ͳɼดϥϦΛ༻͍࣮ͯࡍʹภඍ෼ํఔࣜͷղʹର͢Δ‫ࢉܭ‬۠ؒΛίϯϐϡʔλͰ࡞੒͢Δʹ͸ҎԼͷ 2 ͭͷ‫ػ‬ԉ༻ূ໌๏Λߦ͏ɽ͞ΒʹɼPolicy-based designٕज़͕ඞཁͰ͋Δ:ͷಛ௃Λੜ͔ͨ͠਺஋ઢ‫ܗ‬୅਺ͷ৽͍͠։ൃϞσϧ• ‫ؙ‬ΊϞʔυͷ੍‫ޚ‬ΛఏҊ͢Δ. ຊ࿦จͰ঺հ͢ΔϓϩάϥϜ͸ VCP• ۠ؒԋࢉ

Library ͱͯ͠ http://veriﬁed.computation.jp/ʹ

·ͣɼ‫ؙ‬ΊϞʔυͷ੍‫঺ͯؔ͠ʹޚ‬հ͢ΔɽIEEEެ։͍ͯ͠ΔͨΊɼৄࡉΛ஌Γ͍ͨ৔߹͸ࢀর͞

754 Standard Ͱ͸ʮුಈখ਺఺਺ͷ࢛ଇԋࢉʯɼ‫ٴ‬Ε͍ͨɽVCP Library Ͱ͸ C++11 ΛԾఆ͓ͯ͠

ͼʮฏํࠜʯͷ 5 ͭͷԋࢉ݁Ռʹ‫ݶ‬Γ݁Ռʹର͢Γɼ·ͨεΧϥʔͷ‫ͯؔ͠ʹࢉܭ‬͸ദ໦խӳࢯ͕Δ੾Γࣺͯ΍੾Γ্͛ͳͲͷ‫ؙ‬Ίʹؔ͢ΔϞʔυ࡞੒ͨ͠ kv Library Λར༻͢Δ͜ͱ΋૝ఆͯ͠࡞

͕ఆΊΒΕ͍ͯΔɽଈͪɼsin ΍ cos ͳͲͷॳ౳ؔ੒͍ͯ͠Δ [3]ɽ਺ʹؔͯ͠͸ར༻Ͱ͖ͳ͍ͷͰɼผͷํ๏͕ඞཁ
ʹͳΔͷͰ஫ҙ͕ඞཁͰ͋Δɽ

ୈ 2 ষͰ͸ɼਫ਼౓อূ෇͖਺஋‫ؔ͢ʹࢉܭ‬Δ‫ط‬ྫ͑͹ a, b ∈ F ͱͨ͠ͱ͖ɼ࢛ଇԋࢉ͸ҎԼͷଘͷ݁Ռͱͯ͠ɼʮεΧϥʔʹର͢Δਫ਼౓อূ෇
͖਺஋‫ࢉܭ‬ͷ‫͋Ͱૅج‬Δ‫ػ‬ց۠ؒԋࢉʯͱɼʮεΧ௨ΓͰ͋Δɿ

ϥʔʹର͢Δਫ਼౓อূ෇͖਺஋‫ࢉܭ‬ͷ‫ݶ‬քͱͦͷ্޲͖‫ؙ‬Ί:◦ : F × F → F ͱ͠ɼinf{x ∈F | x ≥ a ◦ b}ղܾࡦͰ͋Δࣄ‫ࠩޡޙ‬ධՁʯʹ͍ͭͯ঺հ͢ΔɽԼ޲͖‫ؙ‬Ί:ୈ 3 ষͰ͸ɼఆٛ 1 Λຬͨ͢਺஋ઢ‫ܗ‬୅਺ϥΠϒ◦ : F × F → F ͱ͠ɼsup{x ∈F | x ≤ a ◦ b}ϥϦͷઃ‫ํܭ‬๏ʹ͍ͭͯ঺հ͢Δɽୈ 4 ষͰ͸ɼ࠷ۙ఺‫ؙ‬Ί:

Policy-based design ͷಛ௃Λੜ͔ͨ͠਺஋ઢ‫ܗ‬୅਺ͷ৽͍͠։ൃϞσϧʹ͍ͭͯఏҊ͢Δ. ୈ 5 ষ˜◦ : F × F → F ͱ͠ɼ࠷΋͍ۙුಈখ਺఺਺ʹ‫ؙ‬ΊΔɽͰ͸ɼ࣮ࡍʹ Emden ํఔࣜͷఆৗղͱͯ͠ඇࣗ໌

ྫ͑͹ɼҎԼͷΑ͏ʹ C99 ४‫ڌ‬ͷ C ‫ޠݴ‬ίϯύΠղ͕ଘࡏ͢Δ͜ͱΛ‫ػࢉܭ‬Λ༻͍ͯূ໌͢Δ.

ϥͰ͸ fenv.h Λ࢖༻͢Δ͜ͱͰɼ‫ؙ‬ΊϞʔυͷมߋΛߦ͏ fesetround ؔ਺͕ར༻Ͱ͖Δ:

2. εΧϥʔ΍ߦྻͷԋࢉʹؔ͢Δਫ਼౓
อূ෇͖਺஋‫ࢉܭ‬ͷ‫ط‬ଘͷ݁Ռ

# include < fenv .h >͜͜Ͱ͸εΧϥʔ΍ߦྻͷԋࢉʹؔ͢Δਫ਼౓อ

int main ( void ) {ূ෇͖਺஋‫ࢉܭ‬ͷ‫ط‬ଘͷ݁ՌΛࣔ͢. ৄࡉʹ͍ͭ// Լ޲͖‫ؙ‬Ίʹมߋͯ͸ॻ੶ [4] Λࢀߟʹ͞Ε͍ͨ.

fesetround ( FE_DOWNWARD );// ্޲͖‫ؙ‬Ίʹมߋ
fesetround ( FE_UPWARD );2.1 ഒਫ਼౓ුಈখ਺఺਺ʹ͓͚Δ‫ػ‬ց۠ؒԋࢉ// ࠷ۙ఺‫ؙ‬ΊʹมߋR Λ࣮਺શମͷू߹ͱ͠ɼF Λ IEEE 754 Stan-

fesetround ( FE_TONEAREST );dard ͰఆΊΒΕͨഒਫ਼౓ුಈখ਺఺਺ͷू߹ͱ}

͢Δɽୠ͠ɼΦʔόʔϑϩʔ͸‫͜ى‬Βͳ͍ͱԾఆ
͢Δɽ·ͨɼด۠ؒΛ [a, b] := {x ∈ R | a ≤ x ≤ҰํͰɼ‫ؙ‬ΊϞʔυͷมߋ͕؆୯Ͱ͸ͳ͍‫ޠݴ‬b, a, b ∈ R} ͱද‫͢ه‬Δɽ΍ɼͦ΋ͦ΋‫ؙ‬ΊϞʔυͷมߋΛߦ͏͜ͱΛ‫ࢭې‬ਫ਼౓อূ෇͖਺஋‫ࢉܭ‬ͷ‫ج‬ຊ͸ਅͷ஋Λแ‫ؚ͢‬

͍ͯ͠Δ‫͕͋ޠݴ‬ΔͨΊ஫ҙ͕ඞཁͰ͋Δɽ

Δू߹Λ࡞੒͢Δ͜ͱͰ͋Δɽྫ͑͹ 10 ਐ਺ͷΠ‫ؙ‬ΊϞʔυͷมߋΛ༻͍Δ͜ͱͰྫ͑͹ 1/3 ͷ155第59回プログラミング・シンポジウム 2018.1.19-21݁ՌΛแ‫ؚ͢‬Δ۠ؒ [a, b], a, b ∈ F ͸࣍ͷΑ͏ͳ͸Լ޲͖‫ؙ‬ΊͰΛҙຯ͢Δ.

ϓϩάϥϜͰಘΒΕΔ:

࣮ࡍʹ‫ػ‬ց۠ؒԋࢉΛϓϩάϥϜ͢Δʹ͸ɼ্୺ͱԼ୺Λ࣋ͭߏ଄ମ interval ͳͲΛఆٛ͠ɼ͞

# include < fenv .h >Βʹఆٛͨ͠ߏ଄ମ interval ʹର͢Δ‫ػ‬ց࢛۠ؒ

int main ( void ) {ଇԋࢉΛԋࢉࢠଟॏఆٛ౳Λ༻͍࣮ͯ૷͢Δ. kv

double a , b ;Library Ͱ͸্‫ه‬ͷ۠ؒԋࢉΛ͞Βʹվྑ࣮ͨ͠

fesetround ( FE_DOWNWARD );૷ʹͳ͓ͬͯΓɼC++ͷςϯϓϨʔτΛ༻͍ͯ

a = 1.0/ 3.0;

interval < double >, interval < dd >, interval <fesetround ( FE_UPWARD );mpfr < N >> ͳͲͷ double ‫ݶʹܕ‬Βͣߴਫ਼౓ͳ

b = 1.0/ 3.0;}‫ʹࢉܭ‬΋ରԠͰ͖ΔΑ͏ʹͳ͍ͬͯΔ.

ୠ͠ɼ্‫ه‬ͷϓϩάϥϜ͸ίϯύΠϥͷ࠷దԽʹ

2.2 ‫ػ‬ց۠ؒԋࢉͷ‫ݶ‬քͱճආࡦ
‫ػ‬ց۠ؒԋࢉΛར༻͢Ε͹‫ؙ‬Ί‫ࠩޡ‬Λ೺Ѳ͢ΔΑΓϓϩάϥϜͷ࣮ߦॱং͕มߋ͞Εͳ͍͜ͱ͕લఏͱͳΔ*1 ɽ͜ͱ͕ՄೳͰ͋Δ. ͔͠͠ɼ۠ؒԋࢉ͸ԋࢉ͝ͱ͜ͷΑ͏ʹɼුಈখ਺఺਺ಉ࢜ͷԋࢉͰ͋Ε͹‫ؙ‬ʹաେධՁΛߦ͍ͬͯΔͨΊଟ͘ͷ۠ؒԋࢉΛ‫܁‬ΊϞʔυͷมߋʹΑΓ໨తͱ͢Δਅͷ஋Λแ‫ؚ͢‬Δ

Γฦ͢ͱ۠ؒͷ෯͕ඇৗʹେ͖͘ͳͬͯ͠·͏͜ด۠ؒΛಘΔ͜ͱ͕ग़དྷΔɽ࣍ʹɼด۠ؒಉ࢜ͷԋͱ΍ɼ‫ؙ‬ΊϞʔυͷ੍‫͕ޚ‬ଟ͍ͨΊ࣮ߦ͕࣌ؒ௕

ࢉͰ͋Δ۠ؒԋࢉΛఆٛ͢Δඞཁ͕͋Δɽྫ͑͹ɼ

͘ͳΔͳͲͷ໰୊఺͕͋Δ.
ྫ͑͹ɼA ∈ Fn×n , b ∈ Fn ʹ͓͚Δ࿈ཱҰ࣍ํ

2/3 Λแ‫ؚͨ͠‬ด۠ؒΛ [0.666, 0.667]ɼπ Λแ‫ؚ͠‬ͨด۠ؒΛ [3.14, 3.15] ͱͨ͠ͱ͖ɼ2/3 × π ΛಘఔࣜΔʹ͸ด۠ؒಉ࢜ͷੵ [0.666, 0.667] × [3.14, 3.15]

Ax = b͸Ͳͷ༷ʹఆٛ͢Δ͔ͱ͍͏͜ͱͰ͋Δɽ

2 ͭͷด۠ؒ [al , au ], [bl , bu ] ʹର͢Δ‫ػ‬ց۠ؒԋͷਅͷղ x∗ ∈ Rn Λแ‫ؚ͢‬Δ۠ؒϕΫτϧΛ‫ٻ‬ΊࢉΛಋೖ͢Δɽ࢛ଇԋࢉ f : R × R → R ʹର͠ɼ஋Δ໰୊Λߟ͑Δ. ͦͷͱ͖ʹɼGauss ͷফ‫ڈ‬๏ʹ‫ج‬Ҭ f ([al , au ], [bl , bu ]) = {z ∈ R | z = f (x, y), x ∈ͮ͘ΞϧΰϦζϜͰੜ͡Δ‫ࢉܭ‬Λશͯ‫ػ‬ց۠ؒԋ[al , au ], y ∈ [bl , bu ]} Λแ‫ؚ͢‬Δด۠ؒ [cl , cu ] Λ‫ٻ‬ࢉͰ࣮ߦ͢Ε͹ɼಘΒΕͨ݁Ռ͸ਅͷղ x∗ ∈ Rn

ΊΔ͜ͱ͕‫ج‬ຊͰ͋Δ. ҎԼ͕‫ػ‬ց࢛۠ؒଇԋࢉΛแ‫ؚ͢‬Δ۠ؒʹͳΔ. ͔͠͠ɼഒਫ਼౓ුಈখ਺

ͷఆٛͱ͢Δ:఺਺Ͱ‫ػ‬ց۠ؒԋࢉͨ͠ͱͯ͠΋۠ؒ෯͕૿େ͠

Ճࢉɿ [al , au ] + [bl , bu ] := [al +bl , au +bu ]ͯ͠·͏ͨΊʹߟ͍͑ͯΔ໰୊ͷ࣍‫ ͕ݩ‬n ͕਺े‫ࢉݮ‬ɿ [al , au ] − [bl , bu ] := [al −bu , au −bl ]࣍‫ݩ‬ఔ౓͢Βѻ͑ͳ͘ͳͬͯ͠·͏. ྫ͑͹࣍ͷ৐ࢉɿ [al , au ] × [bl , bu ] :=ষͰ঺հ͢Δ VCP Library Λར༻͢Δ͜ͱͰɼ؆

[min{al ×bl , au ×bl , al ×bu , au ×bu },୯ʹࢼ͢͜ͱ͕ग़དྷΔ:

max{al ×bl , au ×bl , al ×bu , au ×bu }]// ྫ 1 VCP Library ( ۠ؒ Gauss )আࢉɿ [al , au ]/[bl , bu ] :=# include < iostream >[min{al /bl , au /bl , al /bu , au /bu },# include < omp .h >max{al /bl , au /bl , al /bu , au /bu }], ͨͩ͠ 0 ∈/# include < kv / interval . hpp >[bl , bu ]# include < kv / rdouble . hpp ># include < vcp / matrix . hpp >͜͜Ͱɼԋࢉࢠ ◦ ʹର͠ ◦ ͸্޲͖‫ؙ‬ΊͰԋࢉɼ◦*1using namespace vcp ;‫ࡏݱ‬͸ C99 ͷ fenv.h ʹ͋Δ‫ؙ‬Ίมߋʹ൐͏࠷దԽͷ཈੍Λߦ͏ FENV ACCESS ͕࣮૷͞Ε͍ͯΔίϯύΠϥ͸গͳ͍ͨΊɼvolatile म০ࢠʹͯ࠷దԽΛ཈੍͢Δ.

int main ( void ) {int n = 50; // Set dimension
matrix < kv :: interval < double > > A , b , x ;156

第59回プログラミング・シンポジウム 2018.1.19-21ͨ͢ਅͷղ x∗ ͱ༩͑ΒΕͨۙࣅղ x̂ ∈ Rn ʹର͠

A . rand ( n ); // Make a random matrix
b . ones (n , 1); // Make vector with 1|x∗ − x̂| ≤ |R(b − Ax̂)| +b = A * b ; // Matrix - vector productx = lss (A , b ); // Solve x s . t . Ax = b

R(b − Ax̂)
|I − RA|eI − RA

std :: cout << x (0) << std :: endl ;͕੒Γཱͭ.

}

࣮ࡍʹ͸ఆཧ 1 ʹ‫ݱ‬ΕΔ R ͸ߦྻ A ͷۙࣅ‫ߦٯ‬͜ͷϓϩάϥϜ͸ n = 50 ͱ͠ɼe = (1, · · · , 1)T ͱྻͱ͠ɼۙࣅղ x̂ ͱۙࣅ‫ ྻߦٯ‬R ͸‫ط‬ଘͷϥΠϒ

͢Δͱ Ae ∈ b ͱ͍ͯ͠ΔͨΊɼAx = b Λຬͨ͢ਅϥϦ౳Λ༻͍ͯ‫ٻ‬Ίͯ‫͢ࢉܭ‬Ε͹ྑ͍. ྫ͑͹࣍ͷղ x∗ ͸ 1 ʹͳΔ. ͞Βʹɼ࿈ཱҰ࣍ํఔࣜͷղΛͷষͰ঺հ͢Δ VCP Library Λར༻͢Δ͜ͱͰɼ‫ٻ‬ΊΔؔ਺ lss() ͸ LU ෼ղʹΑΔલਐফ‫ޙͱڈ‬ୀ؆୯ʹࢼ͢͜ͱ͕ग़དྷΔ:୅ೖʹΑΓղ x Λ‫ٻ‬Ί͍ͯΔͨΊɼશͯͷ‫ػʹࢉܭ‬// ྫ 2 VCP Library ( BLAS , LAPACK , ਫ਼౓อূ )ց۠ؒԋࢉΛར༻͢Δ kv Library ͷ interval ‫ܕ‬ΛςϯϓϨʔτͰ౉͢ͱಘΒΕͨू߹ x ͸ਅͷղ x# include < iostream >∗# include < omp .h >Λแ‫ؚ͢‬Δ݁ՌʹͳΔ͸ͣͰ͋Δ. ͜ͷ݁ՌΛදࣔ# include < kv / interval . hpp >ͯ͠ΈΔͱɼ΋ͪΖΜཚ਺ͷ஋ʹΑͬͯ΋มԽ͢# include < kv / rdouble . hpp >Δ͕ஶऀ͕ࢼͨ͠‫ݶ‬Γɼྫ͑͹ [−224705, 224707]# include < vcp / pidblas . hpp >ͷΑ͏ͳด͕۠ؒಘΒΕͨ. ͜ͷΑ͏ʹ 1 Λแ‫ؚ‬# include < vcp / matrix . hpp >͢Δด۠ؒͰ΋ [−224705, 224707] ͷΑ͏ʹ۠ؒ෯using namespace vcp ;͕େ͖͍۠ؒͰ͸ҙຯ͕ͳ͘ͳͬͯ͠·͏. ·ͨ

int main ( void ) {n = 100 ͱ͢Δͱɼ۠ؒ෯ͷ૿େ͕Ө‫ ͠ڹ‬0 আࢉ

std :: cout . precision (17);
int n = 10000; // dimension͕ൃੜ͠ɼ‫͏·ͯͬ͠ͳ͘ͳ͖Ͱࢉܭ‬.

matrix < kv :: interval < double >,ภඍ෼ํఔࣜͳͲͷԠ༻໰୊ͷۙࣅղΛ‫ٻ‬ΊΔ

pidblas > A , b , x ;ࡍʹ͸࣍‫ݩ‬͸਺ઍ͔Β਺ेສҎ্ʹ·ͰʹొΔՄ

A . rand ( n );ೳੑ͕͋Δ. ͦͷͨΊɼn = 100 ఔ౓Ͱར༻Ͱ͖

b . ones (n , 1);ͳ͘ͳͬͯ͠·͏ͱԠ༻ʹ͸ద͞ͳ͍. ͦ͜Ͱɼb = A*b;x = lss (A , b );ྑ͘஌ΒΕ͍ͯΔճආࡦͱͯ͠ɼ࿈ཱҰ࣍ํఔࣜ

std :: cout << x (0) << std :: endl ;Ax = b ͷۙࣅղ x̂ Λ‫ٻ‬Ί͔ͯΒɼਅͷղ x∗ ͱͷ}ࠩΛ‫͢ࢉܭ‬ΔΞϧΰϦζϜʹ੾Γସ͑Δ. ྫ͑͹ɼۙࣅղ x̂ ͱਅͷղ x∗ ͷࠩΛ‫͢ࢉܭ‬Δఆཧͱͯ͜͠ ͷ ϓ ϩ ά ϥ Ϝ ͸ n = 10000 ͱ ͠ ɼઌ ΄ Ͳ ͱࢁຊͷఆཧ [5] ͕ྑ͘஌ΒΕ͍ͯΔ. C Λߦྻ (orಉ ༷ ʹ ਅ ͷ ղ x∗ ͕ 1 ʹ ͳ Δ Α ͏ ʹ ઃ ఆ ͠ ͯϕΫτϧ) ͱ͠ɼ|C| Λߦྻ (or ϕΫτϧ)C ͷ੒෼͍ Δ.

ຖͷઈର஋Λද͢‫͢ͱ߸ه‬Δ. ·ͨɼC ͱͯ͠

ؒ [0.99999999759705449, 1.0000000023973821] ͱߦྻ (or ϕΫτϧ)C ͷ࠷େ஋ϊϧϜͱ͢Δ.

ͳͬͨ. ͜ͷ஋͸ཚ਺΍ߦྻ A ͷੑ࣭ʹΑΓมԽͦ ͷ ͱ ͖ ɼਅ ͷ ղ x∗ Λ แ ‫ ͢ ؚ‬Δ ด ۠ߦྻ A ∈ Rn×n , ϕΫτ͢Δ͕ɼ௚઀ Gauss ͷফ‫ڈ‬๏ʹ‫ػ‬ց۠ؒԋࢉΛదϧ b ∈ Rn , ߦྻ R ∈ Rn×n ΛͦΕͧΕ༩͑ΒԠͨ͠৔߹Ͱ͸‫ٻ‬ΊΒΕͳ͔ͬͨ 1 ສ࣍‫ݩ‬ͷ໰୊

ఆཧ 1 (ࢁຊͷఆཧ [5])Ε ͯ ͍ Δ ͱ ͢ Δ.

I ∈ R

n×n

Λ୯Ґߦྻͱ͠

Ͱ΋ղ͘͜ͱ͕Մೳʹͳ͍ͬͯΔ.

e = (1, 1, · · · , 1)T ∈ Rn ͸શ੒෼͕ 1 ͷϕΫτ͜ͷΑ͏ʹਫ਼౓อূ෇͖਺஋‫ࢉܭ‬͸ɼʮΑ͘ར༻ϧͱ͢Δ. ΋͠͞ΕΔΞϧΰϦζϜʯ+ʮ‫ػ‬ց۠ؒԋࢉʯͷΑ͏ʹ୯७ʹ͸࣮૷Ͱ͖ͣɼ৽ͨʹ‫ࠩޡ‬Λղੳ͢ΔͨΊI − RA < 1ͷఆཧͷ࣮૷͕ඞཁʹͳΔ.

Λຬͨ͢ͳΒ͹ɼA ͸‫ྻߦٯ‬Λ࣋ͪɼAx = b Λຬ157

第59回プログラミング・シンポジウム 2018.1.19-21

3. ఆٛ 1 Λຬͨ͢਺஋ઢ‫ܗ‬୅਺ϥΠϒϥϦͷߏங

imats < kv :: dd > > A , b , x ;A . rand ( n );b . ones (n , 1);ຊষͰ͸ఆٛ 1 Λຬͨ͢਺஋ઢ‫ܗ‬୅਺ϥΠϒϥb = A*b;

ϦΛ Policy-based design ʹ‫ߏ͍ͯͮج‬ங͢Δ. ਤ

x = lss (A , b );1 ʹ‫͋ࡏݱ‬Δྑ͘஌ΒΕͨ਺஋ઢ‫ܗ‬୅਺ϥΠϒϥ

std :: cout << x (0) << std :: endl ;}Ϧͱఆٛ 1 Λຬͨͨ͢Ίʹඞཁͳ‫ܕ‬ͷ૊Έ߹ΘͤΛࣔ͢.

͜ͷϓϩάϥϜ͸ n = 1000 ͱ͠ɼ࿈ཱҰ࣍ํఔࣜ Ax = b ͷਅͷղ x∗ ͕ 1 ʹͳΔΑ͏ʹઃςʖϩ
ʀ9&3/LEUDU\

ఆ͍ͯ͠Δ. ͦͷͱ͖ɼਅͷղ x∗ Λแ‫ؚ͢‬Δ
ด۠ؒ [0.9999999999999999999999999020023735,

1.00000000000000000000000007358396] ͱͳͬͨ.

߶ଐۛࣇ
GRXEOH‫ܗ‬%/$6/$3$&.ཤ༽
ςʖϩ
ʀ0$7/$%,17/$%ςʖϩʀERRVWXEODVʀ(LJHQۛࣇ൜༽ద͵‫ܗ‬͜ͷ݁Ռ͔Β΋Θ͔ΔΑ͏ʹྫ 2 ͷ৔߹ʹൺ΂

double ͷ‫ݶ‬քਫ਼౓ͷ͓Αͦ 16 ܻΑΓ΋ਫ਼౓͕ྑ߶ଐ੠ౕฯৄGRXEOH‫ܗ‬%/$6/$3$&.ཤ༽

͘ɼ͓Αͦ 25 ܻ·Ͱ 0 ͕ฒͿ݁Ռͱͳͬͨ. Ұํ
ͰɼBLAS ౳ͷ‫ط‬ଘͷߴ଎ͳϓϩάϥϜΛ࢖༻͠੠ౕฯৄ‫ؽ‬փۢؔԍࢋ͗Ն೵൜༽ద͵‫ܗ‬ਤ 1ͳ͍ͨΊɼඇৗʹ‫ͱ͜͏·ֻ͔͕ͯͬؒ࣌͠ࢉܭ‬ʹ஫ҙ͢Δ.
·ͨɼྫ 1 ͔Βྫ 3 ·Ͱ͸ kv Library ͷ‫ػ‬ցఆٛ 1 Λຬͨ͢ϥΠϒϥϦʹඞཁͳ৚݅ͱπʔϧͷ۠ؒԋࢉ‫͋Ͱܕ‬Δ interval ‫ܕ‬Λར༻͍͕ͯͨ͠ɼ

ରԠdouble ‫ܕ‬ͷΈʹ‫ݶ‬ఆ͠ BLAS ͱ LAPACK Λ༻͍ͨߴ଎ͳۙࣅղΛ‫ٻ‬ΊΔ͜ͱ΋ՄೳͰ͋Δ:ਤ 1 ʹ͋ΔΑ͏ʹࠓճ঺հ͢Δ VCP Library ͸શͯͷ‫ܕ‬Λѻ͑ΔΑ͏ʹߏங͍ͯ͠Δ. ྫ͑͹ɼҎ// ྫ 4 VCP Library ( double , BLAS , LAPACK )ԼͷΑ͏ͳϓϩάϥϜͰࠓ·Ͱͷ‫ط‬ଘͷϥΠϒϥ

# include < iostream >Ϧʹ͸ͳ͔ͬͨ‫ػ‬ց۠ؒԋࢉ͕Մೳͳ൚༻తͳ‫ܕ‬# include < omp .h ># include < vcp / pdblas . hpp >ͷਫ਼౓อূ͕ՄೳͱͳΔ. ͜͜Ͱ͸ɼ‫ػ‬ց۠ؒԋ# include < vcp / matrix . hpp >ࢉ͕Մೳͳ൚༻తͳ‫ͯ͠ͱܕ‬ɼkv Library ʹ͋Δusing namespace vcp ;ٙࣅ 4 ഒਫ਼౓‫͋Ͱܕ‬Δ dd ‫ͦͱܕ‬ͷ‫ػ‬ց۠ؒԋࢉ

int main ( void ) {‫ ܕ‬interval ‫ܕ‬Λར༻͍ͯ͠Δ.

std :: cout . precision (17);
int n = 20000; // dimension// ྫ 3 VCP Library ( kv :: dd , ਫ਼౓อূ )matrix < double , pdblas > A , b , x ;# include < iostream >A . rand ( n );# include < omp .h >b . ones (n , 1);# include < kv / interval . hpp >b = A*b;# include < kv / dd . hpp >x = lss (A , b );# include < kv / rdd . hpp >std :: cout << x (0) << std :: endl ;# include < vcp / imats . hpp >}# include < vcp / matrix . hpp >using namespace vcp ;͜ͷϓϩάϥϜ͸ n = 20000 ͱ͠ɼ࿈ཱҰ࣍ํఔ

int main ( void ) {std :: cout . precision (34);ࣜ Ax = b ͷਅͷղ x∗ ͕ 1 ʹͳΔΑ͏ʹઃఆͯ͠

int n = 1000; // dimension

͍Δ. ͜ͷϓϩάϥϜ͸ਫ਼౓อূ෇͖਺஋‫Ͱࢉܭ‬

matrix < kv :: interval < kv :: dd >,͸ͳ͍ͷͰۙࣅղ 1.000000000274329 ͷΑ͏ʹ‫ٻ‬158

第59回プログラミング・シンポジウム 2018.1.19-21

·Δ. ·ͨɼ͜ͷ஋΋ཚ਺ߦྻ A ͕มΘΔຖճͷΞϧΰϦζϜͷ࡞੒ʹઐ೦͢΂͖ Policy Ϋϥ࣮ߦ͝ͱʹมԽ͢Δ.

ε P Ͱ͸ move ίϯετϥΫλΛߟ͑ͳͯ͘
΋ྑ͍Α͏ʹ͢Δɽ

VCP Library ͷྫ 1 ͔Βྫ 4 Λ௨ͯ͠‫ͯݟ‬ΈΔͱΘ͔ΔΑ͏ʹɼม਺ͷ‫ ໊ܕ‬matrix(Host Ϋϥε)ͦͷͨΊɼPolicy Ϋϥε P Λʮ͋ΔܾΊΒΕͨʹೖΕΔςϯϓϨʔτҾ਺ (Policy Ϋϥε) ͱͦ‫ن‬ଇʹ‫ͮ͘ج‬ϝιουม਺ͱϝιουؔ਺ʯΛ࣋ΕʹରԠ͢ΔඞཁͳϔομʔϑΝΠϧͷ includeͭΑ͏ʹ࡞੒͠ɼϢʔβʔ͸ʮPolicy ͷ‫໊ܕ‬ʯͱ͕େ͖͘ҧ͍ͬͯΔ఺ͰɼͦΕҎ֎ʹ͸ຊ࣭తͳʮmatrix ‫( ܕ‬Host Ϋϥε) ͷ࢖͍ํʯ͑͞ཧղ͢Εมߋ͸ͳ͍. ͦͷͨΊɼϢʔβʔ͸ਫ਼౓อূͷ༗͹ɼࣗ༝ʹʮ‫ܕ‬ʯɼʮΞϧΰϦζϜʯɼʮਫ਼౓อূͷ

ແ΍ਫ਼౓ʹؔΘΒͣϢʔβʔࣗ਎͕࣮૷͍ͨ͠

༗ແʯͳͲ͕બ୒ՄೳʹͳΔ (ਤ 2)ɽ

ॏཁͳΞϧΰϦζϜͷϓϩάϥϜʹઐ೦͠ɼඞཁ
ʹԠͯ͡ม਺ͷ‫ܕ‬Λมߋ͢Ε͹ΞϧΰϦζϜ͕ม

3ROLF\έϧηߋͰ͖Δ. ͜ͷ఺͕ Policy-based design Λ༻͍ͨ

൜༽‫ܗ‬
ۛࣇ

VCP Library ͷ matrix Ϋϥεͷಛ௃Ͱ͋Δ. ࿈

PDWUL[έϧηϤʖδʖ

PDWUL[‫ܗ‬

Ϥʖδʖ
ϕϫήϧϞ

GRXEOH‫ܗ‬߶ଐۛࣇཱҰ࣍ํఔࣜͷղΛ‫ٻ‬ΊΔؔ਺Ҏ֎ʹ΋࣮ରশߦྻʹର͢ΔҰൠԽ‫ݻ‬༗஋໰୊ͷ‫ݻ‬༗஋Λ‫ٻ‬ΊΔؔ

൜༽‫ܗ‬
੠ౕฯৄ

਺΋͋ΔͷͰৄࡉ͸ VCP Library ͷ web ϖʔδ

http://veriﬁed.computation.jp/Λࢀর͞Ε͍ͨɽɹɹʀϤʖδʖ͗ཤ༽͢
Ώͤ͏‫ܙ‬Ͷร‫ܙ‬
ʀPRYHαϱηφϧένΝߡྂ

GRXEOH‫ܗ‬߶ଐ੠ౕฯৄʀ਼஍ત‫ܙ‬େ਼͹ΠϩβϨθϞ

3.1 matrix Ϋϥεͷઃ‫ܭ‬
matrix Ϋϥε (Host Ϋϥε) ͸ 2 ͭͷςϯϓϨʔਤ 2

τҾ਺ T ͱ P Λඞཁͱ͠ɼ T ʹ͸ߦྻͷཁૉͷʀԢ༽ద͵ϕϫήϧϞΝࡠ੔ʀPDWUL[έϧη͹࢘͏๏
ʀ3ROLF\έϧη͹‫໌ܗ‬Ͳࣙ༟Ͷʰ‫ܗ‬ʱͳʰ੠ౕฯৄ͹༙ໃʱΝમ୔Ͳ͘Ζ

VCP Library ͷ matrix Ϋϥεͷߟ͑ํ‫ܕ‬ɼ P ʹ͸ߦྻԋࢉʹؔ͢ΔΞϧΰϦζϜΛఆٛͨ͠Ϋϥε (Policy Ϋϥε) Λ༩͑Δ:

3.2 VCP Library ͷ Policy Ϋϥε‫ࡏݱ‬ɼVCP ϥΠϒϥϦͰఏ‫͍ͯ͠ڙ‬Δ Policy Ϋ

vcp :: matrix < _T , _P >ϥε͸ҎԼͷ 4 ͭͰ͋Δ:·ͨɼmatrix Ϋϥε͸ Policy Ϋϥε P Λ‫ܧ‬ঝ͠• mats< T >

͍ͯΔ:

–

T ‫ܕ‬ͷۙࣅ൚༻‫ ܕ‬Policy

template < typename _T , class _P = mats < _T > >• pdblasclass matrix : protected _P {– double ‫ܕ‬ͷߴ଎ۙࣅ Policy...

– BLASɼLAPACK ͕ඞཁ};• imats< T (, P) >matrix Ϋϥε಺Ͱ͸ɼҎԼͷΑ͏ͳ 2 ఺ͷΈ໾ׂ–Λ୲͍ͬͯΔ:– kv ϥΠϒϥϦͷ interval ‫͕ܕ‬ඞཁ–• Policy Ϋϥε P Λ‫ܧ‬ঝ͢Δ͜ͱͰʮ͋Δ‫ن‬

T ‫ܕ‬ͷਫ਼౓อূ൚༻‫ ܕ‬PolicyP ͸ਫ਼౓อূ෇͖਺஋‫Ͱࢉܭ‬ඞཁͱͳΔۙࣅղΛ‫͢ࢉܭ‬Δߦྻ༻ Policyɽ‫ه‬ड़͠ͳ͍৔

ଇʹैͬͯఆٛ͞Ε͍ͯΔϝιουม਺ͱϝ߹͸ P = mats<ιουؔ਺ʯͷΈΛ‫ͼݺ‬ग़͠ɼϢʔβʔ͕རT >ͱͳΔɽ• pidblas༻͠΍͍͢࢓༷ʹม‫͢ܗ‬Δ– double ‫ܕ‬ͷߴ଎ਫ਼౓อূ Policy• matrix Ϋϥε಺ͰͷΈ move ίϯετϥΫλ
(C++11) Λߟ͑ɼ༨෼ͳίϐʔʹΑΔϝϞ

– LAPACK ͱ‫ؙ‬ΊมߋՄͳ BLAS ͕ඞཁϦʔͷѹഭΛ௿‫͠ݮ‬ɼߴ଎ԽΛ͸͔Δɽಛʹɼ

– kv ϥΠϒϥϦͷ interval ‫͕ܕ‬ඞཁ

159

第59回プログラミング・シンポジウム 2018.1.19-21

·ͨɼਤ 3 ʹࣔ͢Α͏ʹ֤ Policy ͷ‫ܧ‬ঝͷؔ܎ϧΰϦζϜͷબ୒͸‫ݱ‬ঢ়ɼ‫ޠݴ‬΍ϥΠϒϥϦͷ։͸ mats ͕ࠜ‫͋ʹװ‬ΔɽͦͷͨΊɼ৽͍͠‫ػ‬ೳΛ௥ൃऀ͕ߦ͍ͬͯΔ. ͦͷͨΊɼϢʔβʔ͸࢖͍ͨՃ͚ͨ͠Ε͹ mats ʹ௥Ճ͠ɼmatrix Ϋϥε͔Β͍ΞϧΰϦζϜΛબ୒͢Δʹ͸‫ޠݴ‬΍ϥΠϒϥϦ

‫ͼݺ‬ग़ͤΔΑ͏ʹ͢Ε͹ɼ͢΂ͯͷ Policy Ͱར༻Λԣஅ͢Δ͔ɼ͋Δ͍͸Ϣʔβʔࣗ਎ͰΞϧΰϦՄೳʹͳΔɽ

ζϜΛ࣮૷͠ͳ͚Ε͹ͳΒͳ͍. ·ͨɼΞϧΰϦζϜ։ൃऀʹͱͬͯ΋ɼ༗໊ͳ‫ޠݴ‬΍ϥΠϒϥϦ
ʹ࣮૷͞Εͳ͍‫ݶ‬Γɼ։ൃऀࣗ਎͕ϥΠϒϥϦΛ

SGEODV࡞੒͢Δ͔ɼ͋Δ͍͸࿦จͷΈͷެ։ʹཹ·ͬͯ
SLGEODVPDWVB7!

͠·͏.

LPDWVB7B3!

ਤ 3

Policy ؒͷ‫ܧ‬ঝͷؔ܎ᩘ್⥺ᙧ௦ᩘ䛾ᚑ᮶䛾㛤Ⓨ䝰䝕䝹·ͨɼඞཁʹԠͯ͡ mats Λ‫ܧ‬ঝͨ͠ Policy ಺Ͱมߋ͍ͨ͠ΞϧΰϦζϜʹؔ͢Δϝιουؔ਺ΠϩβϨθϞ
֋൅ं‫ޢݶ‬ɾϧ΢ϔϧϨ

Λॻ͖‫͑׵‬Ε͹ɼผͷΞϧΰϦζϜΛ࣋ͭ Policy

ཀྵ࿨$

‫ޢݶ‬

ཀྵ࿨%

ϧ΢ϔϧϨ

ཀྵ࿨&ϧ΢ϔϧϨ

Λ࡞੒Ͱ͖ΔɽͦͷͨΊɼPolicy Ϋϥεͷ؅ཧ΍֦ுɼҰ෦ͷΈΞϧΰϦζϜΛมߋ͢ΔͳͲ͕༰қͳઃ‫͋ͯ͠ʹܭ‬Δɽ

4. ਺஋ઢ‫ܗ‬୅਺ͷ৽͍͠։ൃϞσϧʀʀʀ

ୈ 3 ষͰ͸ VCP Library ͷ Policy-based designհͨ͠ɽಛʹɼਤ 4਼஍‫ࢋܯ‬ཀྵ࿨'ཀྵ࿨ຘͶ‫ޢݶ‬ʀϧ΢ϔϧϨΝમ୔ゝㄒ䞉䝷䜲䝤䝷䝸䛜ᩘ್⥺ᙧ௦ᩘ䜰䝹䝂䝸䝈䝮䜢㑅䜆ໃ਼͹ཀྵ࿨Λ༻͍ͨ਺஋ઢ‫ܗ‬୅਺ϥΠϒϥϦͷઃ‫ࢥܭ‬૝Λ঺Ϥʖδʖ਺஋ઢ‫ܗ‬୅਺ͷैདྷͷ։ൃϞσϧ• ਺஋ઢ‫ܗ‬୅਺ͷΞϧΰϦζϜΛ‫ه‬ड़͢Δ PolicyΫϥε• ؔ਺ͷ‫ͼݺ‬ग़͠ํ๏ͳͲͷ࢖͍উखͱϝϞϦʔ࡟‫( ݮ‬move) Λ‫ه‬ड़ͨ͠ matrix Ϋϥε (HostΫϥε)ͦΕʹର͠ɼ਺஋ઢ‫ܗ‬୅਺ͷΞϧΰϦζϜͷ‫ه‬ड़৔ॴΛ Policy Ϋϥεͱͨ͠ϥΠϒϥϦͰ͋ΕͱΘ͚Δ͜ͱͰɼ؅ཧ΍֦ுɼҰ෦ͷΈΞϧΰϦ
ζϜΛมߋ͢ΔͳͲ͕༰қͳઃ‫͋ͯ͠ʹܭ‬Δɽ͹ɼਤ 5 ʹࣔ͢Α͏ͳ։ൃϞσϧ͕ߏஙͰ͖Δ. ਺਺஋ઢ‫ܗ‬୅਺ͷΞϧΰϦζϜͷ‫ه‬ड़৔ॴΛ Pol-஋ઢ‫ܗ‬୅਺ͷΞϧΰϦζϜ։ൃऀ͸‫ط‬ଘͷ Policy

icy Ϋϥεͱͨ͠ϥΠϒϥϦ͸ɼΞϧΰϦζϜΛ

ΫϥεͷҰ෦ͷΈࣗ਎ͷΞϧΰϦζϜʹࠩ͠ସ͑

։ൃ͢Δ‫਺ͱऀڀݚ‬஋ઢ‫ܗ‬୅਺ΛԠ༻͢Δ‫ऀڀݚ‬ͯɼ։ൃऀࣗ਎ͷ Policy ΫϥεΛఏ‫͖Ͱڙ‬ɼࣗ਎ͷ૒ํʹϝϦοτ͕͋Δ. ͜͜Ͱ͸ɼPolicy-basedͷΞϧΰϦζϜΛԠ༻ͯ͘͠ΕΔϢʔβʔ·Ͱ͢design Λ༻͍ͨ਺஋ઢ‫ܗ‬୅਺ϥΠϒϥϦͷಛ௃Λ͙ʹಧ͚Δ͜ͱ͕ՄೳʹͳΔ. ·ͨɼϢʔβʔ͸ੜ͔ͨ͠։ൃϞσϧΛఏҊ͢Δ. ·ͣɼਤ 4 ʹैHost Ϋϥεʹ౉͢ Policy ΫϥεΛมߋͷΈͰɼఏདྷͷ਺஋ઢ‫ܗ‬୅਺ͷ։ൃϞσϧΛࣔ͢. ‫ࡏݱ‬ɼ਺‫͞ڙ‬Ε͍ͯΔ࠷৽ͷΞϧΰϦζϜΛ࢖༻Մೳʹͳ஋ઢ‫ܗ‬୅਺ͷΞϧΰϦζϜ͸ແ਺ʹ͋Δ. ྫ͑͹ɼΔ. ͦͷͨΊɼϢʔβ-͸࡞੒͍ͨ͠‫ʹࢉܭ‬ద੾ͳ

LU ෼ղΛΈͯ΋ Crout ๏΍ Doolittle ๏ɼ͞Βʹ਺஋ઢ‫ܗ‬୅਺ΞϧΰϦζϜΛ࠷‫ܾʹޙ‬ఆ͢Δ͜ͱ

ϒϩοΫԽͷख๏ͳͲଟ‫ʹذ‬ΘͨΔ. ͜ΕΒͷΞ͕ՄೳͰ͋Δ.

160

第59回プログラミング・シンポジウム 2018.1.19-21ᩘ್⥺ᙧ௦ᩘ䛾᪂䛧䛔㛤Ⓨ䝰䝕䝹ΠϩβϨθϞ
֋൅ं
3ROLF\έϧη+RVWέϧηϤʖδʖ਼஍‫ࢋܯ‬

ཀྵ࿨$

ཀྵ࿨%

ϧ΢ϔϧϨ

ཀྵ࿨&

࢘༽๏๑ͳ
ΠϩβϨθϞ͹
‫͙ܪ‬໪

ʀ
ʀ
ʀ

ཀྵ࿨ຘͶ
3ROLF\Νમ୔䝴䞊䝄䞊䛜ᩘ್⥺ᙧ௦ᩘ䜰䝹䝂䝸䝈䝮䜢㑅䜆

ໃ਼͹
ཀྵ࿨

ਤ 5

਺஋ઢ‫ܗ‬୅਺ͷ৽͍͠։ൃϞσϧਤ 6

Emden ํఔࣜͷۙࣅղ (N = 50)

L2 (Ω) Λ Lebesgue 2 ৐Մੵ෼ͳؔ਺શମͷू߹͜ͷΑ͏ʹ Policy-based design Λ༻͍ͨ਺஋ઢ
‫ܗ‬୅਺ϥΠϒϥϦͰ͸ɼ਺஋ઢ‫ܗ‬୅਺ͷΞϧΰϦ

ͱ͠ɼH 1 (Ω) Λ 1 ֊ͷ L2 -Sobolev ۭؒͱ͢Δ. ·ζϜ։ൃऀɾϢʔβʔͱ΋ʹϝϦοτ͕͋Δ։ൃ

ͨɼH01 (Ω) := {u ∈ H01 (Ω) : u = 0 on ∂Ω} ͱ͠ɼϞσϧΛߏங͢Δ͜ͱ͕ՄೳʹͳΔ.

H01 (Ω) ͷ‫ڞ‬໾ۭؒΛ H −1 (Ω) ͱ͢Δ. ͦͷͱ͖ʹɼ

5. Ԡ༻ྫ

Δ͜ͱΛ Newton-Kantorovich ͷఆཧΛ༻͍ͯূ

H01 (Ω) ಺ʹఆৗ Emden ํఔࣜ (1) ͷղ͕ଘࡏ͢໌͢Δ:

VCP Library ͷԠ༻ྫͱ࣮ͯ͠ࡍʹପԁ‫ܕ‬ภඍ

ఆཧ 2 (Newton-Kantorovich ͷఆཧͷ‫)ܥ‬෼ํఔࣜͷղͷ‫ػࢉܭ‬ԉ༻ଘࡏূ໌ΛߦͬͯΈඇઢ‫༻࡞ܗ‬ૉ F : H01 (Ω) → H −1 (Ω) ͱ͠ɼํ2

Δ. ྖҬ Ω = (0, 1) ͱ͠ɼఆৗ Emden ํఔࣜͷ

Dirichlet ‫ڥ‬ք஋໰୊−Δu = u2 in Ω,
u=0ఔ ࣜ F (u) = 0 ͷ ۙ ࣅ ղ Λ û ∈ H01 (Ω) ͱ ͢
Δ. ඇઢ‫༻࡞ܗ‬ૉ F ͷ û ʹ͓͚Δ Fréchet ඍ෼F  [û] : H01 (Ω) → H −1 (Ω) ͸ਖ਼ଇͰ͋Γɼෆ౳ࣜ(1)on ∂Ω,

F  [û]−1 L(H −1 ,H01 ) ≤ Kͷඇࣗ໌ղͷଘࡏΛ‫ػࢉܭ‬Λ༻͍ͯূ໌͢Δ.

Λຬͨ͢ਖ਼ͷఆ਺ K ͕ଘࡏ͢ΔͱԾఆ͢Δ. ·ͨɼ༗‫ݩ࣍ݶ‬ͷ‫ج‬ఈ φi ுΒΕۭͨؒ VN ͱ͠ɼ‫ࢉܭ‬ਖ਼ͷఆ਺ δ Λ࢒ࠩϊϧϜͷ্ք‫ٻͰػ‬ΊΔۙࣅղ û ∈ VN ͸Nû(x, y) =F (û)H −1 ≤ δui,j φi (x)φj (y)i=1,j=1

Λ ຬ ͨ ͢ ͱ ͢ Δ.

ͱ͢Δ. ୠ͠ɼLegendre ଟ߲ࣜ

(−1)i
Pi =
i!



d
dx

i

͢Δ. D Λ D ⊃ B̄ Λຬͨ͢։‫͢ͱٿ‬Δ. ਖ਼ͷఆ

i

i

਺GΛ

x (1 − x) , i = 0, 1, · · ·F  [w1 ] − F  [w2 ]L(H01 ,L2 ) ≤ Gw1 − w2 H01 ,Λ༻͍ͨ‫ج‬ఈφi (x) =B̄ Λ B̄(û, 2Kδ) := {u ∈H01 (Ω) : u − ûH01 ≤ 2Kδ} Λຬͨ͢ด‫ͱٿ‬∀w1 , w2 ∈ DdPi
1x(1 − x)(x), i = 1, 2, · · ·i(i + 1)dx

Λຬͨ͢ͱ͢Δ. ΋͠ɼK 2 δG ≤ 1/2 Λຬͨ͢ͳΛར༻͢Δ. N = 50 ͷͱ͖ͷఆৗ Emden ํఔࣜΒ͹ɼํఔࣜ F (u) = 0 Λຬͨ͢ղ u∗ ∈ H01 (Ω) ͸(1) ͷۙࣅղΛਤ 6 ʹࣔ͢.

ଘࡏ͠ɼ

161

第59回プログラミング・シンポジウム 2018.1.19-21

u∗ − ûH01 ≤1−√

1 − 2K 2 δGKG

ද 2 ղͷ‫ػࢉܭ‬ԉ༻ূ໌๏ͷ݁Ռ
N
K 2 δGu∗ − ûH01(2)

Λຬͨ͢. ͦͷ্Ͱɼղ u∗ ͸ D ಺ʹҰҙͰ͋Δ.
ఆཧ 2 Λར༻͢Δʹ͸ɼఆ਺ K, δ, G Λਫ਼౓อ20

7.93 × 10−6

9.18 × 10−5

40

−11

9.37 × 10−10−121.79 × 10−1160

2

8.09 × 10
1.55 × 10

ূ෇͖਺஋‫ࢉܭ‬Λར༻ͯ͠‫ٻ‬Ίͯɼ͞Βʹ K δG
͕ 1/2 ҎԼͰ͋Ε͹ղͷଘࡏ͕ূ໌Ͱ͖Δ. ͞Βද 3 ʹ࣮ߦ࣌ͷ‫ؒ࣌ࢉܭ‬Λࣔ͢. ‫ؒ࣌ࢉܭ‬͸૿ʹɼۙࣅղ û ͱਅͷղ u∗ ͷ H01 ϊϧϜͷҙຯͰͷ΍͢΄Ͳͷ߲਺Λ૿Ճ͍ͯ͠Δ͜ͱ͕‫ͯݟ‬औΕΔ.

ࠩ΋ෆ౳ࣜ (2) Ͱ‫ࢉܭ‬ՄೳͰ͋Δ. ৄ͍͠ఆ਺ͷಛʹ࠷΋ֻ͕͔࣌ؒΔ‫ࢉܭ‬͸ɼۙࣅղͷ࠷େ஋ͱ‫ٻ‬Ίํ͸ɼࢀߟจ‫[ ݙ‬6], [7], [8], [9], [10] Λࢀর͞࠷খ஋Λ‫ٻ‬ΊΔ‫ͨͬ͋Ͱࢉܭ‬. ͜ͷ‫ࢉܭ‬͸ɼਅʹΕ͍ͨ.

࠷େ஋΍࠷খ஋Λแ‫ؚ͢‬Δ۠ؒΛ࡞੒͢ΔͨΊʹɼۙࣅղ û ͸ kv Library ͷٙࣅ 4 ഒਫ਼౓‫͋Ͱܕ‬Δ

ߦྻ‫ࢉܭ‬͸ར༻Ͱ͖ͣɼεΧϥʔ‫ʹࢉܭ‬ͷΈʹͱdd ‫ܕ‬Λૠೖͨ͠ Policy Ϋϥε mats <kv::dd >ͷ

Ͳ·Γɼ·ͨฒྻ౓΋ඇৗʹߴ͍ͨΊվળ͢Δ༨࿈ཱҰ࣍ํఔࣜͷۙࣅ༻ͷιϧόʔͰ‫ٻ‬Ί͍ͯΔ.

஍͸ࠓͷͱ͜Ζͳ͍. ͦͷͨΊɼ਺஋ઢ‫ܗ‬୅਺Λ͞Βʹఆ਺ K ͸ kv Library ͷ interval <double >ར༻͢Δۙࣅղ΍ఆ਺ K ͷ‫ٻ‬ΊΔ‫ؒ࣌ࢉܭ‬͸ओཁ‫ܕ‬Λૠೖ͠ɼ͞Βʹ BLAS ͱ Lapack Ͱߴ଎ͨ͠

࣌ؒʹͳ͍ͬͯͳ͍͜ͱ͕Θ͔Δ.

ਫ਼౓อূ෇͖਺஋‫༻ࢉܭ‬ͷ Policy Ϋϥε pidblasͷ‫ݻ‬༗஋໰୊ͷιϧόʔΛར༻͍ͯ͠Δ.

ද 3‫ڥ؀ػࢉܭ‬͸ CPU: Intel Xeon Phi ProcessorN

7290(1.5 GHz, 72Core, 288 Thread)ɼMemory:

20

384GByte (DDR4 )ɼOS: CentOS 7.2.1ɼCompiler:40

g++ 4.8.5ɼkv Library 0.4.43[3], Intel MKL ver-60

413523‫[ ؒ࣌ࢉܭ‬msec]

࠷େɾ࠷খ஋

K(N = 40)

9068

79301

16530

2388

58529

544292

20321

16821

1686771

29503

63934

ۙࣅղ

δ

sion 2017 Λར༻ͨ͠.
N = 20, 40, 60 ͷ৔߹ʹ͓͚Δఆ਺ K, δ, G ͷ஋

6. ·ͱΊͱࠓ‫ޙ‬ͷ՝୊Λද 1 ʹɼNewton-Kantorovich ͷఆཧͷे෼৚
݅ K 2 δF ≤ 1/2 ͱ H01 (Ω) ϊϧϜͷҙຯͰͷ‫ࠩޡ‬ຊ࿦จͰ͸ɼภඍ෼ํఔࣜͷղͷ‫ػࢉܭ‬ԉ༻ূ໌∗u − ûH01 Λද 2 ʹࣔ͢. ఆ਺ K ͱ G ͸‫ج‬ఈͷ๏ͷͨΊͷ਺஋ઢ‫ܗ‬୅਺ϥΠϒϥϦΛ Policy-based

߲਺ N ʹΑͬͯେ͖͘มԽ͍ͯ͠ͳ͍. ҰํͰɼ

design ʹ৐ͬऔΓ࡞੒ͨ͠. ·ͨɼPolicy-based࢒ࠩʹ͋ͨΔఆ਺ δ ͸‫ج‬ఈͷ߲਺͕૿͑Δ͝ͱʹ

design ͷಛ௃Λੜ͔ͨ͠਺஋ઢ‫ܗ‬୅਺ͷ৽͍͠։খ͘͞ͳ͍ͬͯΔ͜ͱ͕Θ͔Δ. ·ͨɼ͢΂ͯͷൃϞσϧΛఏҊͨ͠. ͞ΒʹɼԠ༻ͱͯ͠࡞੒͠

৔߹ʹ͓͍ͯ Newton-Kantorovich ͷఆཧͷे෼ͨϥΠϒϥϦΛ༻͍࣮ͯࡍʹ Emden ํఔࣜͷఆ

2

৚݅ K δF ≤ 1/2 Λຬ͍ͨͯ͠ΔͨΊɼۙࣅղͷৗղʹର͢Δ‫ػࢉܭ‬ԉ༻ଘࡏূ໌๏Λߦ͍ɼਅͷपลʹਅͷղ͕ଘࡏ͢Δ͜ͱ͕ূ໌Ͱ͖ͨ. ͞ΒղͷଘࡏੑΛূ໌ͨ͠ɽ

ʹɼH01 (Ω) ϊϧϜͷҙຯͰͷ‫ ࠩޡ‬u∗ − ûH01 ΋‫ݱ‬ঢ় Policy Ͱ͋Δ mats<

T >͕ʮߦྻͷૢ‫ج‬ఈͷ߲਺͕૿͑Δ͝ͱʹখ͘͞ͳ͍ͬͯΔ͜ͱ࡞ʯɼʮߦྻಉ࢜ͷԋࢉʯɼʮεΧϥʔͱߦྻͷԋࢉʯɼ͕‫ͯݟ‬औΕΔ.

ʮ࿈ཱҰ࣍ํఔࣜʯ
ɼʮ‫ݻ‬༗஋໰୊ʯ
ɼʮҰൠԽ‫ݻ‬༗஋໰୊ʯͷ͢΂͕ͯ‫·ؚ‬Ε͍ͯΔͨΊඇৗʹେ͖ͳද 1ϓϩάϥϜͱͳ͍ͬͯΔ. ͦ͜Ͱࠓ‫ޙ‬ͷ՝୊ͱ͠ఆ਺ K, δ, G ͷ݁Ռͯ͸ɼmats<

T >΋؅ཧ͠΍͍͢Α͏ʹ Policy

N

K

δ

G

20

2.063

4.24 × 10−5

4.39 × 10−2Λಋೖ͢Δ͜ͱ΋ՄೳͰ͋Δ. ·ͨɼਫ਼౓อূ෇͖

40

2.063

4.34 × 10−10

4.39 × 10−2਺஋‫ࢉܭ‬ͷςΫχοΫͷҰͭͰ͋ΔҰ෦ͷ‫ࢉܭ‬ͷ

2.063

−12

4.39 × 10−2Έߴਫ਼౓‫ࢉܭ‬Λར༻͢Δ Policy ͸‫ݱ‬ঢ়ͳ͍ͨΊɼ

60

8.26 × 10

162

第59回プログラミング・シンポジウム 2018.1.19-21ࠓ‫ޙ‬ΑΓෳࡶͳภඍ෼ํఔࣜͷղͷଘࡏূ໌Λߦ͏ࡍʹ͸࡞੒͢Δඞཁ͕͋Δ.
ँࣙຊ ‫ ڀ ݚ‬͸ JSPS Պ ‫ ݚ‬අ ɼ՝ ୊ ൪ ߸

16K17651 ͷࢧԉΛड͚ͨ΋ͷͰ͋Δɽ·ͨຊ‫ڀݚ‬͸ɼจ෦Պֶলϙετʮ‫ژ‬ʯ๖ժత՝୊ʮ‫ݶۃ‬ͷ୳‫͢ࢿʹڀ‬Δਫ਼౓อূ෇͖਺஋‫ֶࢉܭ‬ͷల։ͱ௒ߴ
ੑೳ‫ڥ؀ࢉܭ‬ͷ૑੒ʯͷҰ‫ͨ͠ࢪ࣮ͯ͠ͱ؀‬΋ͷͰ͋Δɽ·ͨຊ‫ڀݚ‬͸ɼJSTɼCRESTʮϞσϦϯάͷͨΊͷਫ਼౓อূ෇͖਺஋‫ࢉܭ‬࿦ͷల։ʯͷࢧԉΛड͚ͨ΋ͷͰ͋Δɽkv Library ͷ։ൃऀͰ͋
ΔૣҴాେֶ ദ໦խӳઌੜʹ͸ VCP Library ʹ͍ͭͯଟ͘ͷॿ‫ݴ‬Λ௖͖৺͔Β‫ँײ‬ͷ‫ޚͱͪ࣋ؾ‬ྱΛਃ্͛ͨ͘͠ɺँࣙʹ͔͑ͤͯ͞௖͖·͢ɽࢀߟจ‫ݙ‬[1]

IEEE Standard for Floating-Point Arithmetic,
Std 754-2008, (2008).
[2] S.M. Rump, INTLAB - INTerval LABoratory,
In Tibor Csendes, editor, Developments in Reliable Computing, pp.77104. Kluwer Academic
Publishers, Dordrecht, (1999).
[3] M. Kashiwagi: kv - C++ ʹΑΔਫ਼౓อূ෇͖਺
஋‫ࢉܭ‬ϥΠϒϥϦ, http://veriﬁedby.me/kv/[4] େੴਐҰ: ਫ਼౓อূ෇͖਺஋‫ࢉܭ‬, ίϩφࣾ (2000).
[5] T. Yamamoto: Error Bounds for Approximate
Solutions of Systems of Equations, Japan J.
Appl. Math., 1, 1, pp.157–171 (1984).
[6] M.T. Nakao: A numerical approach to the proofof existence of solutions for elliptic problems,
Japan J. Indust. Appl. Math. 5, pp.313–332(1988).
[7] தඌॆ޺, ౉෦ળོ: ࣮ྫͰֶͿਫ਼౓อূ෇͖਺
஋‫ࢉܭ‬:ཧ࿦ͱ࣮૷, αΠΤϯεࣾ (2011).
[8] M. Plum: Computer-assisted existence proofs for
two-point boundary value problems, Computing.
46, pp.19–34 (1991).
[9] M. Plum: Computer-assisted proofs for semilinear elliptic boundary value problems, Japan J.
Indust. Appl. Math. 26, 2-3, pp.419-442 (2009).
[10] K. Tanaka, A. Takayasu, X. Liu, and S. Oishi:
Veriﬁed norm estimation for the inverse of linear elliptic operators using eigenvalue evaluation,
Japan J. Indust. Appl. Math, 31, 3, pp.665–679(2014).

163