1631124688-fb0b2564726fdb4c51612f2aa6ab974b (848587), страница 3
Текст из файла (страница 3)
. . βn,k,Mn γ ∈ RMn .−1 0pl0 = B0,lr ,γ=0 − метод полусопряженных градиентов.1 − метод полусопряженных невязокУсловия полусопряженности 0, k < nγ −1 k nA Bn,l r , r = σ , k = n .n,γ,lРЕСТАРТОВЫЕ МЕТОДЫ НАИМЕНЬШИХ КВАДРАТОВВ ПОДПРОСТРАНСТВАХ КРЫЛОВАnl = ml, l = 1, 2, ... : r nl = f − Au nl ,n = nl + 1, ..., nl+1 − 1 : рекуррентные формулыū nl = u nl + c1 v n1 + · · · + cl v nl , v nk = u nk − u n0 , n0 = 0r¯nl = f − Aū nl = r nl − Wl c̄ −l , Wl = {w nk = Av nk }Wl c̄ l = r nl , min(¯r nl , r¯nl ) : Wl> Wl c̄ l = Wl> r nl55A = A> : ПРЕДОБУСЛОВЛЕННЫЕ МЕТОДЫСОПРЯЖЕННЫХ ГРАДИЕНТОВ (γ = 0)И СОПРЯЖЕННЫХ НЕВЯЗОК (γ = 1)u n+1 = u n + αn pn , r n+1 = r n − αn Ap n ,αn = σn ρn , σn = Aγ B −1 r n , r n , ρn = (Ap n , Aγ p n ) ,B = B >,p n+1 = B −1 r n+1 +βn p n ,βn = σn+1 σn ,γ = 1 : Ap n+1 = AB −1 r n+1 +βn Ap n , (r n , r n ) ≤ ε2 (f , f ),Φn (r n ) = (Aγ−1 r n , r n )56ОДНОШАГОВЫЕ МЕТОДЫ НАИСКОРЕЙШЕГО СПУСКАИ МИНИМАЛЬНЫХ НЕВЯЗОКAu = f ,Nn+1r 0 = f − Au 0 ,nn= u + τn r ,n = 0, 1, ...
:nr = f − Au n ,Φn(γ) (un ) = (Aγ−1 r n , r n ),γΦ(γ)nnγ = 0, 1τn = (A , r , r )/(A r , Ar n ),(Aγ r n , r n )2(γ)(γ) (γ)≤ ρn Φn−1 , ρn = 1 − γ n(A r , Ar n )(Aγ−1 r n , r n )0 < (Au, u) ≤ M(u, u),ρ(γ)n ≤ 1 − m/M,nγ n0 < (A−1 u, u) ≤ m−1 (u, u) :A = A> : ρ(γ)n ≤ 1 − 2m/M.57МЕТОДЫ ДЕКОМПОЗИЦИИ ОБЛАСТЕЙΩ=P[Ωq , Ω̄q = Ωq[Γq , Γq =Γq,q0 , Ω0 = R d /Ω,q 0 ∈ωqq=1Γq,q0 = ΓqΩ̄0 = Ω0[[\Ω̄q0 , q 0 6= q, Ω0 = R d /Ω,ωq = {q1 , ..., qMq },\\[Γq,0 ,Γ, Γq,0 = ΓqΩ̄0 = ΓqΓ, Γq = Γiq[Γq,q0 , Γq,0 = ΓeqΓiq =q 0 6=058Luq (~r ) = fq , ~r ∈ Ωq , lq,q0 (uq )q 0 ∈ ωq , lq,0 uq αq uq + βqΓq,0Γq 0 ,q= gq,q0 ≡ lq0 ,q (uq0 ),Γq 0 ,q= gq,0 , q = 1, ...P, αq · βq ≥ 0,∂uq ∂uq0 = αq0 uq + βq0 , |αq | + |βq | > 0.∂~nq Γq,q0∂~nq0 Γq0 ,qXAq,r ur = fq , q = 1, ...P,Aq,q uq +r ∈ω̂qСтрелообразная блочная матрицаA1,1...0A = {Aq,r } =...AP+1,1...0A1,P+1............
AP,PAP,P+1............ AP+1,P AP+1,P+159КЛАССИЧЕСКИЙ ПРИМЕР ДЕКОМПОЗИЦИИОБЛАСТИ НА ДВЕ ПОДОБЛАСТИ60ПРИМЕР ДЕКОМПОЗИЦИИ НЕОГРАНИЧЕННОЙОБЛАСТИ ДЛЯ ВНЕШНЕЙ КРАЕВОЙ ЗАДАЧИ61ПРИМЕРЫ 1D-, 2D- И 3D-ДЕКОМПОЗИЦИИ622D-ДЕКОМПОЗИЦИЯ СЕТОЧНОЙ ОБЛАСТИС КАРКАСНОЙ РАЗДЕЛИТЕЛЬНОЙ ПОДОБЛАСТЬЮ63ДЕКОМПОЗИЦИЯ СЕТОЧНОЙ ПОДОБЛАСТИБЕЗ УЗЛОВ-РАЗДЕЛИТЕЛЕЙ64(Bq,q u)l ≡ (al,m + θlXm∈ω/ q= f1 +Xal,m )ul +Xm∈ωqal,m )(θl ul − um )m∈ω/ qСеточный шаблон околограничного узла65al,m um =АДДИТИВНЫЙ МЕТОД ШВАРЦА(БЛОЧНЫЙ АЛГОРИТМ ЯКОБИ)A = {Ak,l }, BAS = diag {Ak,k },−1(f − Au n ) = Tu n + g ,u n+1 = u n + BAS−1−1f,A, g = BAST = I − BASun → u⇒ Āu = f¯, Ā = I − T , f¯ = g ,n→∞r 0 = f¯ − Āu 0 = Tu 0 + g − u 0 = u 1 − u 0 ,XAq,q ubq n = fq −Aq,r ubr n−1 ≡ fbq , q = 1, ..., P; n = 1, 2, ...,r ∈cωqXbr n−1 ,Bq,q ubq n ≡ (Aq,q +Cq,q )ubq n = fq +Cq,q ubq n−1 − r ∈cωq Aq,r un = 1, 2, ....66МЕТОД ГРУБОСЕТОЧНОЙ КОРРЕКЦИИĀu = f¯,NcNcXXu = {ul ≈ ulc =ck ϕk (xl , yl )} = Φû + ψ,ϕk (x, y ) = 1,k=1k=1Ncϕk (Pk 0 ) = δk,k 0 , û = {ck } ∈ R , Nc N,ĀΦû = f¯ − Āψ, Φ = [ϕ1 ...ϕNc ] ∈ RN,Nc ,Âû ≡ ΦT ĀΦû = ΦT f¯ − ΦT Āψ ≡ fˆ ∈ RNc ,Âǔ = ΦT f¯ ≡ fˇ, Â(û − ǔ) = −ΦT Āψ,u ≈ ũ = Φǔ = ΦÂ−1 fˆ = Bc−1 f¯, Bc−1 = Φ(ΦT ĀΦ)−1 ΦT ,u − ũ = (Ā−1 − Bc−1 )f¯, u − ũ = Φû + ψ − Φǔ = ψ − Bc−1 ĀψBc – CGC preconditionerРис.
8. Примеры выбора макроузлов длягрубосеточной коррекции: “000 и “x 00 – узлыбазисных функций 0-го и 1-го порядков68МЕТОДЫ ДЕФЛЯЦИИ И АГРЕГАЦИИВыбор начального приближенияu 0 = u −1 + Bc−1 r −1 , r −1 = f¯ − Āu −1 ,r 0 = f¯ − Āu 0 ⊥Φ = span {ϕ1 , ..., ϕNc }, ΦT r 0 = 0,p 0 = (I − Bc−1 Ar 0 ) → ΦT Āp 0 = 0“Улучшенный” метод сопряженных градиентовu n+1 = u n + αn p n , r n+1 = r n − αn Āp n ,p n+1 = r n+1 + βn p n − Bc−1 Ār n+1 ,αn = (r n , Āγ r n )/(Āγ p n , Ap n ), βn = (r n+1 , Āγ r n+1 )/(r n , Āγ r n ),ΦT r n+1 = 0, ΦT Āp n+1 = 0ЛИТЕРАТУРА1. Абрамян М. Э., Штейнберг В.
Я., Штейнберг О. Б.Технологии распараллеливания программ. Ростов н/Д: Изд-воЮФУ, 2014.2. Богачев К. Ю. Основы параллельных вычислений. М.: ЦПНМГУ, 2002.3. Богачев К. Ю. Основы параллельного программирования.М.: Бином, 2014.4. Воеводин В. В. Параллелизм в алгоритмах и программах.Сб. “Вычислительные процессы и системы”. Вып. 10.
М.:Наука, 1993. С. 253-270.5. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления.Спб.: БХВ Петербург, 2002.6. Воеводин В. В. Вычислительная математика и структураалгоритма. М.: МГУ, 2010.ЛИТЕРАТУРА7. Гандер М.Ж. (M. J. Gander). 50 Years of Time Parallel TimeIntegration, in ’Multiple Shooting and Time DomainDecomposition‘. Ed. by T. Carraro.
Springer Verlag, 2015. 69–14.8. Гергель В. П. Современные языки и технологиипараллельного программирования. М.: Изд-во МГУ, 2012.9. Ершов А. П. Программирование – вторая грамотность.Новосибирск, 2003. Препр. ВЦ СОАН СССР.10. Ершов А. П., Ильин В. П.
Пакеты программ — технологиярешения прикладных задач. Новосибирск, 1976. Препр. ВЦСОАН СССР № 121.11. Ильин В. П. Вычислительная информатика – открытиенауки. Новосибирск: Наука, 1991.12. Ильин В. П. Численные методы решения задачэлектрофизики. М.: Наука, 1985.ЛИТЕРАТУРА13. Ильин В. П. Вычислительная математика и информатика:мировые вызовы и российская “дорожная карта”. Вестник РАН.2015. Т. 85, №2. 107–114,14. Ильин В. П. (Il’in V. P.) On the parallel strategies in mathematicalmodeling. Lect. notes, CCIS, Springer, vol. 753.
2017. 69–81.15. Ильин В. П., Скопин И. Н. О производительности иинтеллектуальности суперкомпьютерного моделирования.Программирование. 2016, № 1. 10–25.16. Карпов В. Е., Лобанов А. И. Численные методы, алгоритмы ипрограммы. Введение в распараллеливание. М.: Физматкнига, 2014.17. Кун Томас.
Структура научных революций. М.: АСТ, 2009.18. Малышкин В. Э., Корнеев В. Д. Параллельноепрограммирование мультикомпьютеров. Новосибирск: НГТУ,2006.ЛИТЕРАТУРА19. Миллер Р., Боксер Л. Последовательные и параллельныеалгоритмы. М.: Бином, Лаборатория знаний, 2006.20. Молчанов И. Н. Ведение в алгоритмы параллельныхвычислений. Киев: Наукова думка, 1990.21. Ортега Дж. Введение в параллельные и векторные методырешения линейных систем.
М.: Мир, 1991.22. Попов Ю. П, Самарский А. А. Вычислительныйэксперимент. Новое в жизни, науке, технике. Сер.: Мат.Кибернетика. М.: Знание, 1983.23. Савельев В. А, Штейнберг Б. Я. Распараллеливаниепрограмм. Ростов нД: ЮФУ, 2008.24. Старченко А. В. Берцун В. Н. Методы параллельныхвычислений. Томск: ТГУ, 2013.25. Богачев К. Ю. Основы параллельных вычислений. М.:МГУ, 2002.ЛИТЕРАТУРА26. Столяров Л.
Н., Абрамов В. М. Начала информатики. Отзадачи к программе. М.: МАКЕТ, 2007.27. Богачев К. Ю. Основы параллельного программирования.М.: Бином, 2014.28. Самарский А. А. Михайлов А. П. Математическоемоделирование. М.: Физматгиз, 2002.29. Шагин И. Архитектура высокопроизводительных компьютерови вычислительных систем.http://www.exelenz.ru/learning/parallel-lections30. Якобовский М. В. Введение в параллельные методырешения задач. М.: Изд-во МГУ, 2013.31.
Яненко Н. Н., Коновалов А. Н., Бугров А. Н., Шустов Г. В.Об организации параллельных вычислений и“распараллеливании ” прогонки // Числ. методы механ.сплошной среды. 1978. Т. 9, № 7. 139–146.ЛИТЕРАТУРА32. Яненко Н. Н., Коновалов А. Н. Некоторые вопросы теориимодульного анализа и параллельного программирования длязадач математической физики и механики сплошной среды.Современные проблемы математической физики ивычислительной математики.
М.: Наука, 1982.33. Яненко Н. Н., Преображенский Н. Г., Разумовский О. С.Методологические проблемы математической физики.Новосибирск: Наука, 1986.75ВОПРОСЫ К БИЛЕТАМ (2019)1. Технологические стадии крупномасштабногокомпьютерного эксперимента2. Архитектуры многопроцессорных вычислительныхсистем (МВС)3. Инструменты программирования на МВСс распределенной памятью. Инструменты гибридногопрограммирования на МВС с иерархической памятью4. История первых вычислительных устройствот Б. Паскаля до Ч. Бэббиджа5. История первых релейных и электронных ВМ6. Поколения ЭВМ в 1950–1980 г.7. Архитектура многопроцессорных вычислительныхсистем.8.
Организация памяти и коммуникаций на МВС.9. Варианты организации параллельных вычислений.76ВОПРОСЫ К БИЛЕТАМ (2019)10. Постпетафлопсные вычислительные системы11. Критерии эффективности распараллеливанияалгоритмов12. Законы Амдала и Густафсона13. Параллельный метод сдваивания14. Умножение матрицы на вектор15. Параллельное умножение матриц16. Классический и встречный методы прогонки17. Методы редукции трехдиагональных СЛАУ18. Метод циклической редукции19.
Явные аппроксимации начально-краевых задач.Неявные аппроксимации начально-краевых задач20. Схемы предиктор-корректор21. Неявные схемы Рунге – Кутты – Радо77ВОПРОСЫ К БИЛЕТАМ (2019)22. Выбор начальных приближений в неявных схемах23. Канонические представления итерационных методов.Модельные СЛАУ24. Общие характеристики итерационных методов.Блочные алгоритмы25. Параллельные двучленные методы чебышевскогоускорения26. Трехчленные методы чебышевского ускорения27.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
