Реферат
Дипломна робота: 72 с., 8 рис., 5 табл., 1 додаток, 23 джерела.
Мета роботи – розробка алгоритму та програми чисельного розв'язку систем лінійних алгебраїчних рівнянь з розрідженою матрицею.
При виконанні роботи використані програми Microsoft Office Word 2007 Service Pack 1, Microsoft Office PowerPoint 2007 Service Pack 1 та Microsoft Visual Studio 2008 Service Pack 1, а також основні поняття лінійної алгебри та математичного моделювання.
В результаті роботи розроблена програма чисельного розв'язку систем лінійних алгебраїчних рівнянь з розрідженою матрицею, яка економно витрачає оперативну пам'ять, що дозволяє розв’язувати багато систем високих ступенів за допомогою персональних комп'ютерів. Для розв'язання таких систем при класичній схемі зберігання всіх елементів матриці в оперативній пам'яті довелось би залучати суперкомп'ютери.
СИСТЕМА ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ, ОПЕРАТИВНА ПАМ'ЯТЬ, МАТРИЦЯ, АЛГОРИТМ, ПРОГРАМА.
Зміст
Перелік умовних скорочень і термінів
Вступ
1 Огляд методів розв’язку СЛАР, що виникають у МСЕ
1.1 Точні методи розв’язку СЛАР
1.1.1 Метод Гауса
1.1.2 Метод Крамера
1.1.3 Метод головних елементів
1.1.4 Схема Халецького
1.1.5 Метод квадратного кореня
1.1.6 Метод прогону
1.1.7 Матричний метод
1.2 Ітераційні методи розв’язку СЛАР
2.1 Метод простих ітерацій
1.2.2 Метод Зейделя
1.2.3 Метод релаксації
1.2.4 Багатосітковий метод
1.2.5 Метод Ланцоша
2 Схеми компактного зберігання розріджених матриць
2.1 Перша схема
2.2 Друга схема
3 Оптимізація обчислень
4 Чисельні експерименти
4.1 Пружне деформування тонкостінної просторової рами
4.2 Контактна взаємодія оболонкової конструкції і ложемента
Висновки
Перелік посилань
Додаток А
Перелік умовних скорочень і термінів
1. Умовні скорочення
МСЕ – метод скінчених елементів.
СЛАР – система лінійних алгебраїчних рівнянь.
2. Терміни
Розмірність матриці – кількість невідомих в матриці.
Розріджена матриця – матриця, в якій більшість елементів дорівнює нулю.
Оперативна пам'ять – енергозалежний вид пам'яті комп'ютера, в якій зберігаються дані, необхідні процесору в даний час.
Крайова задача – система диференціальних рівнянь з визначеними лінійними співвідношеннями між значеннями шуканих функцій на кінцях інтервала інтегрування.
Вступ
Зараз у зв'язку з бурхливим розвитком обчислювальних засобів широке поширення одержали інформаційні технології, що мають різноманітну теоретичну і прикладну спрямованість. Серед них особливе місце займають системи автоматизованого проектування (САПР), невід'ємну частину яких становлять підсистеми математичного моделювання різних фізичних процесів. Одним із самих перспективних напрямків розвитку математичного моделювання є широке використання чисельних методів, таких як метод скінчених елементів (МСЕ). Це чисельний метод для диференціальних рівнянь, що зустрічаються у фізиці [1]. Виникнення цього методу пов'язане з розв’язком задач космічних досліджень. Уперше він був опублікований у роботі Тернера, Клужа, Мартіна і Топпа. Ця робота сприяла появі інших робіт; був опублікований ряд статей із застосуванням методу скінчених елементів до задач будівельної механіки і механіки суцільних середовищ. Важливий внесок у теоретичну розробку методу зробив в 1963 р. Мелош, який показав, що метод скінчених елементів можна розглядати як один з варіантів добре відомого методу Релєя-Рітца. У будівельній механіці метод скінчених елементів мінімізацією потенційної енергії дозволяє звести задачу до системи лінійних рівнянь рівноваги [2,3].
Однією з існуючих труднощів, що виникають при чисельній реалізації розв’язку контактних задач теорії пружності методом скінчених елементів, є розв’язок систем лінійних алгебраїчних рівнянь (СЛАР) великої розмірності виду />. За умови зберігання всіх елементів матриці A в оперативній пам'яті навіть комп'ютер з 24 ГБ оперативної пам'яті здатен вирішити СЛАР з кількістю невідомих не більше 56755. Якщо ж невідомих більше, доведеться залучати суперкомп'ютер. Тому актуальною є проблема знаходження схеми компактнішого зберігання матриці СЛАР в оперативній пам'яті.
Зараз розроблена велика кількість програмних систем, що автоматизують різні аспекти чисельного моделювання проблем механіки (ANSYS, COSMOS, FORTU, МІРЕЛА, ПОЛЕ, ПРОЧНОСТЬ і ін.).
Одним з головних блоків усіх цих систем є модуль, відповідальний за розв’язок СЛАР. Слід зазначити, що звичайно розв’язок СЛАР займає більшість часу розрахунку задачі на комп'ютері. Крім того, від цього етапу прямо залежить якість і точність розв’язку задачі в цілому. Тому від вибору методу розв’язку СЛАР і алгоритму його реалізації багато в чому залежить подальший успіх чисельного розрахунку задачі МСЕ.
Більшість існуючих методів розв’язку СЛАР в МСЕ розроблені в припущенні того, що матриця A має стрічкову структуру, причому ширина стрічки m
1. Огляд методів розв’язку СЛАР, що виникають у МСЕ
У процесі побудови дискретних аналогів крайових задач виникають великі системи в загальному випадку нелінійних алгебраїчних рівнянь, які вирішуються у два етапи: на першому етапі вони линеаризуються, а потім отримана система лінійних рівнянь вирішується за допомогою якого-небудь методу лінійної алгебри. Якщо збіжність не досягнута, то процес повторюється.
Основна ідея методу скінчених елементів полягає в тому, що будь-яку неперервну величину, таку як температура, тиск і переміщення, можна апроксимувати дискретною моделлю, яка будується на множині кусочно-неперервних функцій, визначених на кінцевім числі підобластей. Кусочно-неперервні функції визначаються за допомогою значень неперервної величини в кінцевім числі точок розглядаємої області [1,2,3].
У загальному випадку, неперервна величина заздалегідь невідома, і потрібно визначити значення цієї величини в деяких внутрішніх точках області. Дискретну модель, однак, дуже легко побудувати, якщо спочатку припустити, що числові значення цієї величини в кожній внутрішній точці області відомі. Після цього можна перейти до загального випадку. Отже, при побудові конкретної моделі неперервної величини роблять наступним чином:
а) у розглядаємій області фіксується кінцеве число точок. Ці точки називаються вузловими точками або просто вузлами;
б) значення неперервної величини в кожній вузловій точці вважається змінною, яка повинна бути визначена;
в) область визначення неперервної величини розбивається на кінцеве число підобластей, називаних елементами. Ці елементи мають загальні вузлові точки і у сукупності апроксимують форму області;
г) неперервна величина апроксимується на кожному елементі функцією, яка визначається за допомогою вузлових значень цієї величини. Для кожного елемента визначається своя функція, але функції підбираються таким чином, щоб зберігалася неперервність величини уздовж границь елемента.
Способи розв’язку СЛАР, застосовувані разом із МСЕ, можна умовно розбити на дві групи: прямі (точні) і ітераційні (наближені). Прийнято вважати, що прямі методи найбільш ефективні при рішенні СЛАР невисоких порядків (не більше 105невідомих), а ітераційні – для розв’язку СЛАР великих і надвеликих систем (понад 105невідомих).
Якщо всю матрицю коефіцієнтів СЛАР вдається розмістити в пам'яті, то розв’язок такої системи не представляє якої-небудь складності. Однак на практиці часто доводиться мати справу з матрицями, розміри яких суттєво перевищують об'єм оперативної пам'яті комп'ютера. У таких випадках і доводиться використовувати різні модифікації як прямих, так і ітераційних методів.
Остаточне рішення про застосування прямих або ітераційних методів розв’язку СЛАР необхідно ухвалювати на основі аналізу структури досліджуваної математичної задачі. Прямі методи розв’язку СЛАР вигідніше використовувати, якщо необхідно розв’язувати багато однакових систем з різними правими частинами, або якщо матриця А не є додатньо-визначеною. Крім того, існують задачі з такою структурою матриці, для якої прямі методи завжди кращі, ніж ітераційні.
1.1 Точні методи розв’язку СЛАР
Розглянемо ряд точних методів розв’язку СЛАР [4,5].
1.1.1 Метод Гауса
Нехай дана система, де A – матриця розмірності m×m (квадратна). У припущенні, що a11≠0, перше рівняння системи
/>--PAGE_BREAK--
/>
ділимо на коефіцієнт a11, у результаті одержуємо рівняння:
/>
/>
Потімзкожногозіншихрівняньвіднімаєтьсяпершерівняння, помножененавідповіднийкоефіцієнтai1. У результаті ці рівняння перетворяться до виду:
/>
/>
Перше невідоме виявилося виключеним із усіх рівнянь, крім першого. Далі в припущенні, що, ділимо друге рівняння на коефіцієнт /> і виключаємо невідоме з усіх рівнянь, починаючи з третього і т.д. У результаті послідовного виключення невідомих, матриця системи рівнянь стане трикутною:
/>
/>
Сукупність проведених обчислень називається прямим ходом методу Гауса.
З m-го рівняння системи визначаємо xm, з (m-1)-го рівняння визначаємо xm-1 і т.д. до x1. Сукупність таких обчислень називають зворотнім ходом методу Гауса.
Реалізація прямого методу Гауса вимагає N~2m2/3 арифметичних операцій, а зворотнього – N~m2 арифметичних операцій.
1.1.2 Метод Крамера
Нехай дана система лінійних рівнянь, в якій число рівнянь дорівнює числу невідомих:
/>
/>
Припустимо, що визначник системи d≠0. Якщо тепер замінити послідовно у визначнику стовпці коефіцієнтів при невідомих xj стовпцем вільних членів bi, то вийдуть відповідно n визначників d1,...,dn.
Теорема Крамера. Система n лінійних рівнянь з n невідомими, визначник якої відмінний від нуля, завжди сумісна і має єдиний розв’язок, який обчислюється по формулах:
/>
/>
Розв’язок довільних систем лінійних рівнянь. Нехай
/>/>
довільна система лінійних рівнянь, де число m рівнянь системи менше числа n невідомих. Тоді в матриці СЛАР знайдуться r≤m лінійно незалежних рядків, а інші m-r рядків виявляться їхніми лінійними комбінаціями. Перестановкою рівнянь можна добитися того, що ці r лінійно незалежних рядків займуть перші r місць.
Звідси випливає, що кожне з останніх m-r рівнянь системи (1.7) можна представити як суму перших r рівнянь (які називаються лінійно незалежними або базисними), узятих з деякими коефіцієнтами. Тоді система еквівалентна наступній системі r рівнянь з n невідомими:
/>
/>
Припустимо, щомінорr-ї розмірності, складенийзкоефіцієнтівприпершихrневідомих, відміннийвіднуля: Мr≠0, тобтоєбазисниммінором. Уцьомувипадкуневідомі, коефіцієнтиприякихскладаютьбазисниймінор, називаютьсябазисниминевідомими, аіншіn-r– вільниминевідомими.
У кожному з рівнянь системи (1.8) перенесемо в праву частину всі члени з вільними невідомими xr+1,...,xn. Тоді одержимо систему, яка містить r рівнянь з r базисними невідомими. Оскільки визначник цієї системи є базисний мінор Mr, то система має єдиний розв’язок щодо базисних невідомих, який можна знайти по формулах Крамера. Даючи вільним невідомим довільні числові значення, одержимо загальний розв’язок вихідної системи.
Однорідна система лінійних рівнянь. Нехай дана однорідна система лінійних рівнянь з n невідомими:
/>
/>
Оскількидодаваннястовпцязнулівнезмінюєрангуматрицісистеми, тонапідставітеоремиКронекера-Kaпeлліцясистемазавждисуміснаімає, принаймні, нульовий розв’язок. Якщо визначник системи відмінний від нуля і число рівнянь системи дорівнює числу невідомих, то по теоремі Крамера нульовий розв’язок є єдиним.
У тому випадку, коли ранг матриці системи менше числа невідомих, дана система крім нульового розв’язку буде мати і ненульові розв’язки. Для знаходження цих розв’язків у системі (1.9) виділяємо rn лінійно незалежних рівнянь, інші відкидаємо. У виділених рівняннях у лівій частині залишаємо r базисних невідомих, а інші n-r вільних невідомих переносимо в праву частину. Тоді приходимо до системи, розв’язуючи яку по формулах Крамера, виразимо r базисних невідомих x1,..., хr через n-r вільних невідомих.
1.1.3 Метод головних елементів
Нехай дана система n лінійних рівнянь з n невідомими:
/>
/>
де елементи aij(i,j=1,…,n) утворюють розширену матрицю системи. Виберемо найбільший по модулю і не належачий стовпцю вільних членів елемент apq матриці/>, який називається головним елементом, і обчислимо множники mi=-aiq/apq для всіх рядків з номерами i≠p (р-й рядок, що містить головний елемент, називається головним рядком).
Далі до кожного другорядного i-го рядку додамо головний рядок, помножений на відповідний множник mi.
У результаті одержимо нову матрицю, усі елементи q-го стовпця якої, крім apq, складаються з нулів.
Відкинувши цей стовпець і головний p-й рядок, одержимо нову матрицю, число рядків і стовпців якої на одиницю менше. Повторюємо ті ж операції з отриманою матрицею, після чого одержуємо нову матрицю і т.д.
Таким чином, побудуємо послідовність матриць. Для визначення невідомих xj поєднуємо в систему всі головні рядки, починаючи з останнього.
Викладений метод розв’язку систем лінійних рівнянь називається методом головних елементів. Необхідна умова його застосування полягає в тому, що визначник матриці не дорівнює нулю [6,7].
1.1.4 Схема Халецького
Нехай система лінійних алгебраїчних рівнянь дана в матричному вигляді: />, де А – квадратна матриця розмірності n;, – вектори-стовпці.
Представимо матрицю А у вигляді добутку нижньої трикутної матриці С і верхньої трикутної матриці В з одиничною діагоналлю, тобто А=СВ, де
/>
Причому елементи сij і bij визначаються по формулах:
/>
/>/>/>
Рівняння можна записати в наступному вигляді:
/>
/>
Добуток матриці B на вектор-стовпець /> є вектором-стовпцем, який позначимо через :
/>
/>
Тоді рівняння (1.13) перепишемо у вигляді:
/>
/>
Тут елементи сij відомі, тому що матриця А системи /> вважається вже розкладеною на добуток двох трикутних матриць С і В. продолжение
--PAGE_BREAK--
Перемноживши матриці в лівій частині рівності (1.15), одержуємо систему рівнянь, з якої одержимо наступні формули для визначення невідомих:
/>
/>Невідомі yi зручно обчислювати разом з елементами bij.
Після того, як усі yi визначені по формулах (1.16), підставляємо їх у рівняння (1.14) [8].
Оскільки коефіцієнти bij визначені в (1.12), то значення невідомих, починаючи з останнього, обчислюємо по наступних формулах:
/>
/>
1.1.5 Метод квадратного кореня
Даний метод використовується для розв’язку систем лінійних алгебраїчних рівнянь виду
/>
/>
у яких матриця А симетрична, тобто АТ=А, aij=aji(i=j=1,...,n).
Розв’язок системи (1.18) здійснюється у два етапи.
Прямий хід. Перетворення матриці А і представлення її у вигляді добутку двох взаємно транспонованих трикутних матриць:
/>
/>
де
/>
Перемножуючи SТ і S, і дорівнюючи матриці А, одержимо наступні формули для визначення sij:
/>
/>
Після знаходження матриці S систему (1.18) заміняємо двома їй еквівалентними системами з трикутними матрицями (1.19):
/>
/>
Зворотній хід. Записуємо системи (1.21) у розгорнутому виді:
/>
/>
/>
/>
Використовуючи (1.22) і (1.23) послідовно знаходимо:
/>
/>
/>
/>
1.1.6 Метод прогону
Для розв’язку систем виду /> або, що те ж саме,
/>
/>
використовується метод прогону, заснований на припущенні, що шукані невідомі зв'язані рекурентним співвідношенням:
/>
де i=1,…,n-1.
Використовуючицеспіввідношення, виразимоxi-1іxiчерезxi+1іпідставимоврівняння(1.26):
/>/>
де Fi – права частина i-го рівняння. Це співвідношення буде виконуватися незалежно від розв’язку, якщо зажадати
/>
/>
/>
/>
Звідси випливає:
/>
/>/>
/>
З першого рівняння одержимо:
/>
/>
/>
/>
Після знаходження прогоночних коефіцієнтів α і β, використовуючи рівняння (1.27), одержимо розв’язок системи. При цьому
/>
/>
1.1.7 Матричний метод
Матричний метод розв’язку систем лінійних алгебраїчних рівнянь з ненульовим визначником полягає в наступному.
Нехай дана система n лінійних рівнянь з n невідомими (над довільним полем):
/>
/>
Тоді її можна переписати в матричній формі: ,де A–основна матриця системи, і –стовпці вільних членів і рішень системи відповідно:
/>
Помножимо це матричне рівняння ліворуч на A-1–матрицю, зворотню до матриці A:
/>
/>
Оскільки A−1A=E(враховуючи асоциативність матричного добутку), одержуємо . Права частина цього рівняння дасть стовпець рішень вихідної системи. Умовою застосовності даного методу (як і взагалі існування розв’язку неоднорідної системи лінійних рівнянь із числом рівнянь, рівним числу невідомих) є невирідженість матриці A. Необхідною і достатньою умовою цього є нерівність нулю визначника матриці A: det A≠0.
Для однорідної системи лінійних рівнянь, тобто коли />, дійсно зворотнє правило: система />має нетривіальний (тобто ненульовий) розв’язок тільки якщо det A=0. Такий зв'язок між рішеннями однорідних і неоднорідних систем лінійних рівнянь зветься альтернативою Фредгольма.
До прямих методів, що використовують властивість розрідженості матриці, можна віднести: алгоритм мінімального ступеня, алгоритм мінімального дефіциту, деревовидна блокова розбивка для асиметричного розкладання, методи вкладених або паралельних перетинів і ін.
1.2 Ітераційні методи розв’язку СЛАР
Наближені методи розв’язку систем лінійних рівнянь дозволяють одержувати значення коренів системи із заданою точністю у вигляді границі послідовності деяких векторів. Процес побудови такої послідовності називається ітераційним (повторюваним).
Ефективність застосування наближених методів залежить від вибору початкового вектора і швидкості збіжності процесу.
1.2.1 Метод простих ітерацій
Нехай дана система n лінійних рівнянь з n невідомими:. Припускаючи, що діагональні елементи aii≠0 (i=1,...,n), виразимо x1 через перше рівняння системи, x2 – через друге рівняння і т.д. У результаті одержимо систему:
/>
/>
Позначимо bi/aij=βi-aij/aii=αij, де i,j=1,...,n. Тоді система запишеться, таким чином, у матричній формі: x=β+αx. Розв'яжемо цю систему методом простих ітерацій. За нульове наближення приймемо стовпець вільних членів. Кожне (k+1)-е наближення обчислюють по формулі: продолжение
--PAGE_BREAK--
/>
/>
Якщо послідовність наближень x(0),...,x(k) має границю />, то ця границя є розв’язком системи, оскільки в силу властивості границі />, тобто x=β+αx [4,6].
1.2.2 Метод Зейделя
Метод Зейделя являє собою модифікацію методу простих ітерацій.
Нехай дана СЛАР, приведена до нормального вигляду: x=β+αx. Вибираємо довільно початкові наближення невідомих і підставляємо в перше рівняння системи. Отримане перше наближення підставляємо в друге рівняння системи і так далі до останнього рівняння. Аналогічно будуємо другі, треті і т.д. ітерації.
Таким чином, припускаючи, що k-і наближення відомі, методом Зейделя будуємо (k+1)-і наближення по наступних формулах:
/>
/>/>
/>
/>
/>
1.2.3 Метод релаксації
Метод релаксації – наближений метод розв’язку систем лінійних рівнянь.
Система лінійних рівнянь
/>/>
приводиться до виду:
/>
/>
де
/>
Знаходяться нев'язки Rj:
/>
/>
Вибирається початкове наближення x(0)=0. На кожному кроці необхідно перетворити на нуль максимальну нев'язку:
/>
/>
Умова зупинки: />.
Відповідь знаходиться по формулі:
/>
/>
1.2.4 Багатосітковий метод
Багатосітковий метод – метод розв’язку систем лінійних алгебраїчних рівнянь, заснований на використанні послідовності зменшуваних сіток і операторів переходу від однієї сітки до іншої. Сітки будуються на основі більших значень у матриці системи, що дозволяє використовувати цей метод при рішенні еліптичних рівнянь навіть на нерегулярних сітках.
Припустимо, що необхідно розв'язати систему виду:
/>
/>
де A – n×n матриця з елементами aij. Для зручності зіставимо індекси з вузлами сітки, таким чином ui являє собою значення u у вузлі i. Множину вузлів сітки позначимо як Ω={1,2,…,n}. Основна ідея багатосіткових методів полягає в тому, що помилка, яка не може бути усунута методами релаксації, повинна бути прибрана за допомогою корекції з розв’язку на грубій сітці.
Використовуючи верхній індекс як номер рівня введемо наступні позначення:
Послідовність сіток />, причому
/>
СітковіоператориA=A1,A2,…,AM.
Оператори інтерполяції Pk, k=1,2,…,M-1.
Оператори згладжування Sk, k=1,2,…,M-1.
Усі ці компоненти багатосіткового методу будуються на першому етапі, відомому як етап побудови.
Етап побудови.
Дорівняти k=1.
Розділити Ωk на непересічні множини Ck і Fk.
Дорівняти Ωk+1=Ck.
Побудувати оператор інтерполяції Pk.
Побудувати Ak+1=(Pk)TAkPk.
Побудувати якщо необхідно Sk.
Якщо сітка Ωk досить мала, дорівняти M=k+1 і зупинитися. Інакше k=k+1 і перехід на крок 2.
Як тільки етап побудови завершений, може бути визначений рекурсивний цикл побудови розв’язку.
Алгоритм: MGV(Ak, Pk, Sk, uk, fk).
Якщо k=M, розв'язати AMuM=fM використовуючи прямий метод.
Інакше.
Застосувати метод релаксації Skμ1 раз до Akuk=fk.
Зробити корекцію на грубій сітці.
Обчислити rk=fk−Akuk.
Обчислити rk+1=(Pk)Trk.
Застосувати MGV(Ak+1, Pk+1, Sk+1, ek+1, rk+1).
Обновити розв’язок uk=uk+Pkek+1.
Застосувати метод релаксації Skμ2 раз до Akuk=fk.
Вищенаведений алгоритм описує V(µ1, µ2) – цикл.
Вибір послідовності сіток і оператора інтерполяції є найбільш важливим елементом етапу побудови і багато в чому визначає якість багатосіткового методу. Критерієм якості є дві вимірювані величини: фактор збіжності – що показує, наскільки швидко сходиться метод, тобто яка кількість ітерацій потрібна для досягнення заданої точності; складність оператора – визначає кількість операцій і об'єм пам'яті, необхідної для кожної ітерації методу.
Складність оператора Cop розраховується як відношення кількості ненульових елементів у всіх матрицях Ak, k=1,2,…,n до кількості ненульових елементів у матриці першого рівня A1=A.
1.2.5 Метод Ланцоша
Для розв’язку СЛАР високої розмірності, матриця коефіцієнтів якої зберігається в компактному нижчеописаному вигляді, найбільш зручним ітераційним методом є метод Ланцоша [4], схема якого має вигляд:
/>
/>
/>
/>
деai=(ri-1,ri-1)/(Asi,si), bi=(ri,ri)/(ri-1,ri-1).
Перевагою даного методу є його висока швидкість збіжності до точного розв’язку. Крім того, доведено, що він має властивість «квадратичного закінчення», тобто для додатньо визначеної матриці можна гарантовано одержати точний розв’язок при кількості ітерацій k≤n. Розмір необхідної пам'яті на кожній ітерації не змінюється, тому що не вимагає перетворення матриці A. За критерій зупинки даного ітераційного процесу звичайно використовують співвідношення:
/>
продолжение
--PAGE_BREAK--
/>
деε– заданаточність. Заіншийкритерійзбіжностіінодізручнішевикористовуватисередньоквадратичнурізницюміжрішеннями, отриманиминасусідніхітераціях:
/>/>
Середньоквадратичну різницю необхідно контролювати при виконанні кожних k наперед заданих ітерацій.
Недоліком методу Ланцоша є сильна залежність збіжності від точності обчислення напрямів спуску.
Практика показує, що при рішенні СЛАР із сильно розрідженими матрицями коефіцієнтів метод Ланцоша має досить високу збіжність, причому в якості початкового наближення можна брати будь-які числа (наприклад, нулі або праву частину).
2. Схеми компактного зберігання розріджених матриць
Одним з важливих достоїнств МСЕ є те, що в результаті його застосування, як правило, виникають позитивно визначені, симетричні і добре обумовлені матриці коефіцієнтів. Крім того, вони звичайно мають таку важливу властивість, як низька щільність, що при правильній нумерації вузлів кінцево-елементної розбивки тіла приводить до групування ненульових елементів стрічкою певної ширини уздовж головної діагоналі. Це і пояснює той факт, що більшість методів розв’язку СЛАР, застосовуваних разом із МСЕ, орієнтована на розв’язок систем зі стрічковою структурою матриці коефіцієнтів.
Симетричність матриці коефіцієнтів дозволяє не запам'ятовувати майже половину її елементів, а при рішенні СЛАР зменшити об'єм обчислень і, як наслідок, знизити кількість помилок округлення.
На жаль, існують цілі класи задач, для яких ширина стрічки прагне до її порядку. Наприклад, при дослідженні за допомогою МСЕ контактних задач механіки деформованого твердого тіла, у яких у взаємодії беруть участь більше двох тіл, ширина стрічки дорівнює розмірності глобальної матриці жорсткості всіх контактуючих тіл. Тому при більших порядках СЛАР ітераційні методи розв’язку часто виявляються кращими.
У деяких ситуаціях, наприклад, при моделюванні динамічних процесів, доводиться розв’язувати велику кількість систем рівнянь з однієї і тою же матрицею коефіцієнтів. У цьому випадку вартість прямої схеми може збігатися з вартістю розв’язку трикутної системи при відомому розкладанні, оскільки вартістю єдиного розкладання, віднесеного до всіх систем, можна знехтувати. У цих ситуаціях часто вірно і те, що число ітерацій, необхідних ітераційній схемі, дуже невелике, оскільки є хорошіпочаткові вектори.
Усі ці факти, а також простота програмної реалізації більшості ітераційних методів розв’язку СЛАР і обумовлюють їхню популярність.
Застосування ітераційних методів дозволяє суттєво скоротити витрати оперативної пам'яті комп'ютера за рахунок того, що при формуванні глобальної матриці жорсткості досить фіксувати тільки її ненульові елементи. У зв'язку з цим при використанні кінцево-елементної технології виникає проблема розробки ефективних алгоритмів формування, зберігання і використання розріджених матриць.
Пам'ять, використовувана для зберігання розріджених матриць, складається з двох частин: основної пам'яті, у якій утримуються числові значення елементів матриць, і додаткової пам'яті, де зберігаються вказівники, індекси і інша інформація, необхідна для формування структури матриць і яка забезпечує доступ до числових значень їх елементів при виконанні процедур формування і розв’язку СЛАР, тобто так звані списки зв'язності. Способи зберігання і використання даних, що зберігаються в основній і додатковій пам'яті, досить різноманітні і визначаються, головним чином, обраним методом розв’язку СЛАР. Для структурної побудови інформації, що зберігається в додатковій пам'яті – списків зв'язності – широко використовується теорія графів.
Особливо складні алгоритми роботи з розрідженими матрицями виникають при використанні прямих методів розв’язку. У першу чергу це пов'язане з тим, що при розкладанні розрідженої матриці A=LLT вона звичайно зазнає деякого заповнення, тобто нижній трикутний множник L має ненульові елементи в тих позиціях, де у вихідній матриці A стояли нулі (не виключено, що при цьому можуть з'явитися і нові нульові елементи). Крім того, прямі методи вимагають спеціальної нумерації вузлів кінцево-елементної сітки, яка забезпечує мінімальну ширину стрічки. Подібних проблем при використанні ітераційних методів не виникає [10,11].
У рамках даної роботи стосовно ітераційних методів розв’язку СЛАР викладені 2 алгоритми зберігання і використання розріджених матриць, які відрізняються простотою реалізації і високою обчислювальною ефективністю.
2.1 Перша схема
Матриця жорсткості, що виходить при застосуванні МСЕ, має симетричну структуру, що дозволяє в загальному випадку зберігати тільки верхню трикутну частину матриці. Однак для задач із великою кількістю невідомих це також приводить до проблеми нестачі пам'яті. Викладений у даній роботі метод дозволяє зберігати тільки ненульові члени матриці жорсткості. Суть його полягає в наступному.
Спочатку, з метою виявлення зв'язків кожного вузла з іншими, проводиться аналіз структури дискретизації області на КЕ. Наприклад, для КЕ-сітки, зображеної на рис. 2.1, відповідна структура зв'язків буде мати вигляд, зображений у табл. 2.1.
Таблиця 2.1 – Структура зв'язків КЕ-сітки
№ вузла
1
2
3
4
5
6
7
Зв'язки
1,2,5,6,7
1,2,3,6
2,3,4,6
3,4,5,6,7
1,4,5,7
1,2,3,4,6,7
1,4,5,6,7
Тоді для зберігання матриці жорсткості необхідно построчно запам'ятовувати інформацію про коефіцієнти, відповідні до вузлів, з якими зв'язаний даний вузол. На рис. 2.2 наведені матриця жорсткості і її компактний вигляд для сітки, зображеної на рис. 2.1 [9].
Текст програми, що реалізує викладений алгоритм аналізу структури КЕ-розбивки тіла, наведений у додатку А [12,13].
/>Даний спосіб компактного зберігання матриці жорсткості дозволяє легко його використовувати разом з яким-небудь чисельним методом. Найбільш зручним для цієї мети здається використання вищевикладеного ітераційного методу Ланцоша, тому що на кожній ітерації потрібно тільки перемножувати матрицю коефіцієнтів СЛАР і заданий вектор. Отже, для використання запропонованого методу компактного зберігання матриці СЛАР необхідно побудувати пряме і зворотнє перетворення в первісну квадратну матрицю.
Нехай aij – елемент первісної квадратної матриці розмірністю n×n, а – її компактний вигляд. Тоді для зворотнього перетворення будуть слушні наступні співвідношення:
/>
/>
/>
/>
/>/>
/>
де m – кількість ступенів волі (m=1,2,3).
Для прямого перетворення будуть слушні співвідношення, зворотні до співвідношень (2.1) – (2.4).
2.2 Друга схема
При реалізації ітераційного розв’язку системи рівнянь досить частою є ситуація, коли необхідно виконати множення матриці системи Aна який-небудь вектор, наприклад, на вектор вузлових невідомих або на вектор нев'язки />, де [20]. Побудова добутків типу або є одним з вузьких місць ефективної реалізації всього ітераційного процесу розв’язку системи рівнянь, оскільки вимагає найбільших витрат процесорного часу. Нижче представлений алгоритм побудови добутку і безпосередньо пов'язаний з ним спосіб компактного зберігання матриці A [14–16].
/>
Рисунок 2.3 – Кінцево-елементна модель
Розглянемо як приклад кінцево-елементну модель, зображену на рис. 2.3. З кожним вузлом сітки зв'язане деяке число вузлів, які можуть бути розбиті на дві множини: першу множину становлять вузли, номери яких менше i – номера розглядаємого вузла, а друга множина – вузли, номери яких більше i. У табл. 2.2 зображена структура матриці СЛАР, відповідна до вузлових зв'язків кінцево-елементної моделі, представленої на рис. 2.3.
Таблиця 2.2 – Структура матриці СЛАР
1
2
3
4
5
6
7
8
9 продолжение
--PAGE_BREAK----PAGE_BREAK----PAGE_BREAK--
4
3
5
4
5
2
5
13
5
5
6
7
6
1
6
15
6
6
7
11
7
4
7
1
7
3
8
12
8
5
8
18
8
7
9
13
9
2
9
8
10
1
10
9
11
4
11
6
12
7
12
5
13
7
13
9
14
8
14
6
15
4
15
9
16
6
16
8
17
5
17
9
18
9
Рисунок 2.5 – Структура векторів-вказівників
У тих рідких випадках, коли той або інший розглядаємий вузол кінцево-елементної моделі не має зв'язку з вузлами, номера яких менше або більше номера даного вузла, тоді у відповідні гнізда векторів або заносяться нулі. Наприклад, вузол 4 (див. рис. 2.3) не має зв'язку з вузлами, номера яких менше 4, це враховується записом нуля в гніздо 4 вектора (рис. 2.5). Вузол 3 не має зв'язку з вузлами, номера яких більше 3 – цій обставині відповідає запис нуля в гніздо 3 вектора />. Виключення становить запис в 1-е гніздо вектора , куди заноситься номер останнього гнізда вектора />. Для всіх інших вузлів ці параметри визначаються тривіально. Для кожної кінцево-елементної моделі інформаційні вектори будуються один раз – відразу ж після того, як закінчена побудова масиву, що описує кінцеві елементи сітки.
Структура вектора (див. рис. 2.4) у значній мірі повторює структуру вектора />. Ненульові наддіагональні елементи aijматриці Aзберігаються у векторі порядково, а порядок їх розміщення в межах рядка визначається порядком розміщення індексів у векторі />.
Тепер розглянемо побудову сум добутків, що входять у рівняння (2.5). Розгляд почнемо з другої суми, а саме:
/>
/>
При фіксованому індексі iвизначаються номери першого і останнього гнізд вектора />, у яких розміщаються номери вузлів, пов'язаних з j-м вузлом, і для яких j>i. Наприклад, для вузла 5 (див. рис. 2.3) маємо: номер 1-го гнізда 13, а номер останнього гнізда 14=15-1. Номера першого і останнього гнізд визначають у векторі />діапазон розміщення ненульових елементів матриці A, які приймають участь у добутках суми (2.6). Крім того, ці ж номера гнізд визначають у векторі діапазон розміщення номерів відповідних елементів xiвектора . Таким чином, наприклад, для вузла 5 сума (2.6) складається з двох додатків:
/>
/>
Побудова першої суми з рівняння (2.5)
/> продолжение
--PAGE_BREAK--
/>
алгоритмічно виконується складніше. При фіксованому номері iвизначаються номери першого n і останнього m (njвузлів, пов'язаних з вузлом i, і для яких j. Цим самим задаються компоненти xiвектора . Тепер необхідно визначити елементи aij=aji(i≠j)матриці A, що зберігаються у векторі . Ця процедура виконується в такий спосіб. Послідовно з гнізд із n по m у векторі беруться номери вузлів j (j. По цих номерах jз вектора />визначаються номери першого k і останнього l (kjу діапазоні гнізд (l–k) вектора перебуває номер i, оскільки, по-перше, вузол iпов'язаний з кожним вузлом j, а, по-друге, i>j. Переглядаючи гнізда вектора />і порівнюючи номера вузлів, що перебувають у цих гніздах, з номером i, можна визначити номер гнізда, у якому для даного вузла jі його діапазону номерів гнізд (l–k) перебуває номер вузла i. По номеру гнізда вузла iу векторі />можна знайти у векторі елемент aij=aji(i≠j, j.
Розглянемо приклад. Побудуємо суму (2.8) для вузла 5 кінцево-елементної моделі, зображеної на рис. 2.3. Із цим вузлом, як ми вже відзначали вище, зв'язані вузли 4, 2 і 1. Номера цих вузлів зберігаються у векторі />у гніздах з 4 по 6, причому їх номера менше 5. Таким чином, компоненти вектора відомі: х4, х2і x1. Визначимо елементи матриці A. Вузлу 4 у векторі />відповідають гнізда з 8 по 12. У цих гніздах зберігаються номери вузлів, пов'язаних з номером 4, причому всі ці номери більше 4. Один із цих номерів –5. Цей номер перебуває в гнізді вектора з номером 12. У гнізді з цим же номером 12 у векторі зберігається елемент a45=a54(j=4матриці А. Аналогічно відшукуються елементи a25(j=2і a15(j=1. Таким чином, одержуємо вираз для />:
/>
/>
Остаточно з урахуванням (2.7) уся сума S5має такий вигляд:
/>
Із представленого вище алгоритму видно, що обчислювальні витрати на побудову сум добутків і />різні. Друга сума будується значно швидше. Це пов'язано з тим, що при побудові першої суми необхідно проводити додатковий порівняльний аналіз номерів вузлів, розміщених у векторі />. При розгляді процедур алгоритму передбачалося, що всі необхідні дані розташовуються в оперативній пам'яті комп'ютера. Довжина одномірних масивів, у яких розміщаються вектори />, і , залежить від структури розглядаємої кінцево-елементної моделі. У табл. 2.3 представлені дані по розмірності цих векторів для трьох типів кінцево-елементних моделей, побудованих у результаті розбивки одиничного куба на 20-вузлові квадратичні елементи. Куб розбивався в наступних пропорціях: 5:5:5 (КЕМ № 1), 10:10:10 (КЕМ № 2) і 20:20:20 (КЕМ № 3).
Таблиця 2.3 – Розмірність векторів КЕМ
Номер КЕМ
Число вузлів
Число елементів
/>
/>
/>
1
756
125
16079
16071
16079
2
4961
1000
121709
121691
121709
3
35721
8000
946619
946619
946619
Порівняння даного алгоритму з алгоритмами, розглянутими в роботах [17–19], показує наступне. Для реалізації запропонованого алгоритму потрібно більше оперативної пам'яті, оскільки для координування ненульових елементів використовуються не два масиви (вектори номерів рядків і стовпців), а чотири. Додаткові вектори і, розмірності яких не перевищують числа діагональних елементів, дозволяють локалізувати зони пошуку елементів-співмножників при побудові сум (2.6) і (2.8). За рахунок цього досягається економія часових витрат на розв’язок СЛАР.
На закінчення відзначу, що викладений вище алгоритм формування сум у рівнянні (2.5) може бути повністю застосований і для побудови інших аналогічних матричних добутків, необхідних для реалізації ітераційних процесів.
3 Оптимізація обчислень
Задача вирішення систем рівнянь виду досить поширена. Вона виникає при описі декількох процесів, кожний з яких описується лінійним рівнянням. Сюди відноситься вивчення процесів, що протікають у лінійних електричних схемах, апроксимація систем диференціальних рівнянь, зокрема, які описують процеси теплопровідності.
Процедура розв’язку великої системи рівнянь на одному процесорі приводить до значних витрат часу. Побудова багатопроцесорної обчислювальної системи не завжди є доступним і оптимальним рішенням. З підвищенням надійності і швидкодії сучасних комп'ютерних мереж з'явилася можливість розв’язку подібних завдань у розподіленім обчислювальнім середовищі [21,22].
Оскільки компоненти середовища фізично рознесені в просторі, то кожний процес має локальну пам'ять і використання глобальних структур даних неможливо. Така схема взаємодії припускає обмін повідомленнями між процесами.
Пропонується будувати взаємодію між процесами по наступному принципу. Є деякий процес, який одержує дані від користувача. Він проводить попередню обробку цих даних. Потім процес формує повідомлення і розсилає їх необхідному числу допоміжних процесів, які виконують безпосередні обчислення. Відповідь повертається першому процесу у вигляді повідомлень від допоміжних процесів. Тут відбувається аналіз результатів обчислень і, при необхідності, процедура повторюється. Такий принцип взаємодії процесів зветься «керуючий-робітники». Перший процес є керуючим, допоміжні процеси – це робітники [23].
Існує кілька технологій побудови розподілених обчислювальних систем. Одна з перших, технологія RPC (Remote Procedure Call), заснована на віддалених викликах процедур. Процесу дозволяється викликати процедури, реалізовані на іншому, віддаленому комп'ютері. При цьому параметри процедури передаються на віддалений комп'ютер, там здійснюється виконання процедури і результати вертаються в місце виклику.
Технологія COM (Component Object Model) – це об'єктна модель компонентів. Вона застосовується для зв'язку між компонентами і програмами, а також при описі API і взаємодії різних мов і середовищ програмування. Одним з головних аспектів технології COM є реалізація клієнт-серверних додатків за допомогою інтерфейсів. В COM-програму входять COM-сервер, COM-клієнт і COM-інтерфейс.
COM-сервер – програма або бібліотека, яка надає деякі служби програмі-клієнтові. COM-сервер містить один або кілька COM-об'єктів. Кожний COM-об'єкт реалізує одну або кілька служб. Кожна служба описується інтерфейсом.
COM-клієнт – програма, яка використовує служби COM-сервера, запитуючи при цьому описані інтерфейси.
COM-інтерфейс – абстрактний клас, що описує властивості і методи COM-об'єкта. Клієнт через інтерфейс об'єкта може використовувати його методи і властивості як свої власні.
Існує також технологія CORBA (Common Object Request Broker Architecture) – узагальнена архітектура брокера об'єктних запитів. Дана технологія також заснована на ключовому понятті інтерфейсу. Об'єкт надає службу. Клієнт звертається до неї, використовуючи інтерфейс.
У технологіях COM і CORBA реалізована ідея розподілених об'єктів (distributed objects). При цьому інтерфейс служить універсальним засобом взаємодії. Розподілені об'єкти розміщаються на різних комп'ютерах. Коли процес викликає метод, реалізація інтерфейсу на машині з процесом перетворює виклик методу в повідомлення, передане об'єкту. Об'єкт виконує запит і повертає результати. Реалізація інтерфейсу перетворює відповідне повідомлення в повертаєме значення, яке передається викликаючому процесу. продолжение
--PAGE_BREAK--
Реалізація розподіленої системи, що розв’язує систему рівнянь виду />, можлива засобами технології COM. Перенос моделі «керуючий-робітники» на COM означає наступне. Керуючий процес повинен бути реалізований як COM-клієнт, робочі процеси, що виконують обчислення, реалізуються як COM-сервера послуги, що надають свої послуги через інтерфейси. COM-клієнт приймає вихідну систему від користувача, виконує перетворення до виду, зручного для ітерації, ділить систему на блоки, розсилає частини вихідних даних COM-серверам, використовуючи їх інтерфейси. Коли відповідь отримана, клієнт виконує збирання результатів і аналіз точності отриманого розв’язку. При досягненні заданої точності процес обчислень припиняється. Важливо, що в цьому випадку COM-клієнт реалізується як одиночна програма, що використовує послуги декількох віддалених COM-серверів.
У свою чергу, COM-сервера містять COM-об'єкти, які і реалізують функціональність, що забезпечує розв’язок систем виду /> ітераційними методами.
Слід зазначити, що при такій реалізації розв’язок окремих блоків рівнянь вихідної системи здійснюється на різних хостах розподіленої системи. Це дозволяє робити обчислення паралельно і незалежно, що значно скорочує час розв’язку в порівнянні з обчисленнями на однопроцесорній системі.
4. Чисельні експерименти
Була розв’язана задача з кількістю невідомих, що перевищує чотири мільйона та проведене порівняння ефективності прямих і ітераційних методів. Конфігурація тестового комп'ютера наведена в табл. 4.1.
Таблиця 4.1 – Конфігурація тестового комп'ютера
Мікропроцесор
Intel Core 2 Duo E7200 (Socket LGA775, 3172 МГц)
Оперативна пам'ять
4*(Kingston ValueRAM KVR667D2N5/1G) (4ГБ)
Системна плата
ASUS P5K (Socket LGA775, Intel P35+ICH9)
ОС
Microsoft Windows Vista Ultimate x64 SP1
4.1 Пружне деформування тонкостінної просторової рами
Була розглянута задача про пружне деформування тонкостінної просторової рами (рис. 4.1) при наступних геометричних параметрах: L=H=2м, L1=1,98м, L2=0,01м. Пружні властивості матеріалу рами: E=106Па, ν=0,3. Зовнішнє навантаження P=102Н.
Кінцево-елементна модель усієї конструкції містила 1449604 вузла і 4374320 скінчених елементів у формі тетраедра. СЛАР розв’язувалася з використанням першої схеми. Час розв’язку склав близько двох годин.
4.2 Контактна взаємодія оболонкової конструкції і ложемента
Була вирішена задача про контактну взаємодію оболонкової конструкції і ложемента (рис. 4.2).
Дана задача часто виникає на практиці. При транспортуванні або зберіганні з горизонтальним розташуванням осі оболонкові конструкції встановлюються на кругові опори – ложементи. Взаємодія підкріплених оболонкових конструкцій і ложементів здійснюється через опорні шпангоути, довжина яких уздовж вісі оболонки порівняна з шириною ложементів і багато менше радіуса оболонки і величини зони контакту.
Дискретна модель ложемента (у тривимірній постановці) представлена на рис. 4.3.
При побудові даної КЕ-моделі було використано 6689 вузлів і 15323 КЕ у формі тетраедра. Розмір нестиснутої матриці жорсткості для такої задачі становить (6689*3)2*8=3221475912 байт, що приблизно дорівнює 3 ГБ оперативної пам'яті.
Задача розв’язувалася двома способами – методом Гауса і методом Ланцоша. Порівняння результатів розв’язку наведено в табл. 4.2.
Таблиця 4.2 – Результати розв’язку
Метод Гауса
Метод Ланцоша
Час розв’язку, (сек.)
3137
2194
З табл. 4.2 легко бачити, що час розв’язку методом Ланцоша значно менше, ніж у випадку використання методу Гауса.
Висновки
У даній роботі розглянуті способи компактного зберігання матриці коефіцієнтів системи лінійних алгебраїчних рівнянь і методи розв’язку СЛАР. Розглянуті алгоритми компактного зберігання матриці жорсткості дозволяють значно скоротити об'єм необхідної пам'яті для зберігання матриці жорсткості.
Класичні методи зберігання, що враховують симетричну і стрічкову структуру матриць жорсткості, що виникають при застосуванні методу скінчених елементів, як правило, не застосовні при рішенні контактних задач, тому що при їхньому рішенні матриці жорсткості декількох тіл поєднуються в одну загальну матрицю, ширина стрічки якої може прагнути до розмірності системи.
Викладені у роботі методи компактного зберігання матриці коефіцієнтів СЛАР дозволяють на прикладі розв’язку контактних задач досягти значної економії оперативної пам'яті. Це дозволяє розв’язувати системи з мільйонами невідомих на сучасних персональних комп'ютерах.
Вважаю, що для оптимальної продуктивності при розв’язку СЛАР високих ступенів треба використовувати 24 ГБ оперативної пам'яті стандарту DDRIII 1333, мікропроцесор Intel Core i7-965 Extreme Edition, системну плату ASUS Rampage II Extreme, дві відеокарти AMD Radeon HD 4870X2 та твердотільний накопичувач OCZ Summit. Потужність такої конфігурації може скласти близько 5 терафлопс, що досить непогано. Для пришвидшення розрахунків вважаю доцільним розгін мікропроцесора, використання у програмі спеціалізованих наборів інструкцій процесорів по роботі з числами з плаваючою крапкою та використання у програмі ресурсів відеопроцесора відеокарти, за умови оптимізації програми під такі нововведення. Також значно пришвидшити розрахунки допоможе використання більшої кількості процесорів (або процесорних ядер).
Наведені алгоритми розв’язку СЛАР високих ступенів у задачах механіки можуть ефективно застосовуватися для аналізу тривимірних задач високої розмірності, що особливо актуально в задачах сучасного машинобудування.
Перелік посилань
Зенкевич О., Морган К. Конечные методы и аппроксимация. – М.: Мир, 1980. – 479 с.
Зенкевич О. Метод конечных элементов. – М.: Мир, 1975. – 217 с.
Стрэнг Г., Фикс Дж. Теория метода конечных элементов. – М.: Мир, 1977. – 346 с.
Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. – М.: Наука, 1987. – 632 с.
Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. – М.: Наука, 1984. – 176 с.
Бахвалов Н.С. Численные методы. – М.: Наука, 1975. – 153 с.
Годунов С.К. Решение систем линейных уравнений. – Новосибирск: Наука, 1980. – 81 с.
Gustavson F.G. Some basic techniques for solving sparse matrix algorithms. – New York: Plenum Press, 1972. – 215 p.
Джордж А., Лиу Дж. Численное решение больших разрежённых систем уравнений. – М.: Мир, 1984. – 333 с.
Rose D.J. A graph theoretic study of the numerical solution of sparse positive definite system of linear equations. – New York: Academic Press, 1972. – 473 p.
Мосаковский В.И., Гудрамович В.С., Макеев Е.М. Контактные задачи теории оболочек и стержней. – М.: Машиностроение, 1978. – 718 с.
Рвачев В.Л., Шевченко А.Н. Проблемно-ориентированные языки и системы для инженерных расчётов. – К.: Техніка, 1988. – 198 с.
Голуб Дж., Ван Лоун Ч. Матричные вычисления. – М.: Мир, 1999. – 548 с.
Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. – М.: Наука, 1986. – 288 с.
Тьюарсон Р. Разрежённые матрицы. – М.: Мир, 1977. – 191 с.
Брамеллер А., Аллан Р., Хэмэм Я. Слабозаполненные матрицы. – М.: Энергия, 1979. – 192 с.
Эстербю О., Златев 3. Прямые методы для разрежённых матриц. – М.: Мир, 1987. – 120 с.
Писсанецки С. Технология разреженных матриц. – М.: Мир, 1988. – 410 с.
Сабоннадьер Ж.-К., Кулон Ж.-Л. Метод конечных элементов и САПР. – М.: Мир, 1989. – 192 с.
Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. – М.: Наука, 1978. – 592 с.
Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. – М.: Мир, 1991. – 347 с.
Валях Е. Последовательно-параллельные вычисления. – М.: Мир, 1985. – 216 с.
Таненбаум Э., Ван Стеен М. Распределённые системы. Принципы и парадигмы. – СПб.: Питер, 2003. – 481 с.
Додаток А
Вихідний текст програмирозв’язку СЛАР з розрідженою матрицею
#include
#include
#include
#include
#include продолжение
--PAGE_BREAK--
#include «matrix.h»
#include «smatrix.h»
#define BASE3D_4 4
#define BASE3D_8 8
#define BASE3D_10 10
const double Eps=1.0E-10;
DWORD CurrentType=BASE3D_10;
class RVector
{
private:
Vector Buffer;
public:
RVector() {}
~RVector() {}
RVector(DWORD Size) { Buffer.ReSize(Size); }
RVector(RVector &right) { Buffer=right.Buffer; }
RVector(Vector &right) { Buffer=right; }
DWORD Size(void) { return Buffer.Size(); }
void ReSize(DWORD Size) { Buffer.ReSize(Size); }
double& operator[] (DWORD i) { return Buffer[i]; }
RVector& operator=(RVector &right) { Buffer=right.Buffer; return * this; }
RVector& operator=(Vector &right) { Buffer=right; return * this; }
void Sub(RVector&);
void Sub(RVector&, double);
void Mul(double);
void Add(RVector&);
friend double Norm(RVector&, RVector&);
};
class TSMatrix
{
private:
Vector Right;
Vector * Array;
Vector * Links;
int Dim;
DWORD Size;
public:
TSMatrix(void) { Size=0; Dim=0; Array=NULL; Links=NULL; }
TSMatrix(Vector *, DWORD, int);
~TSMatrix(void) { if (Array) delete [] Array; }
Vector &GetRight(void) { return Right; }
DWORD GetSize(void) { return Size; }
int GetDim(void) { return Dim; }
Vector &GetVector(DWORD i) { return Array[i]; }
Vector * GetLinks(void) { return Links; }
void SetLinks(Vector * l) { Links=l; }
void Add(Matrix&,Vector&);
void Add(DWORD I, DWORD L, DWORD J, DWORD K, double v)
{
DWORD Row=I, Col=L*Links[I].Size()*Dim+Find(I, J)*Dim+K;
Array[Row][Col]+ v;
}
void Add(DWORD I, double v) { Right[I]+=v; }
DWORD Find(DWORD, DWORD);
void Restore(Matrix&);
void Set(DWORD, DWORD, double, bool);
void Set(DWORD Index1, DWORD Index2, double value)
{
DWORD I=Index1/Dim, L=Index1%Dim, J=Index2/Dim, K=Index2%Dim, Pos=Find(I, J), Row=I, Col;
if (Pos==DWORD(-1)) return;
Col=L*Links[I].Size()*Dim+Find(I, J)*Dim+K;
Array[Row][Col]=value;
}
bool Get(DWORD Index1, DWORD Index2, double &value)
{
DWORD I=Index1/Dim, L=Index1%Dim, J=Index2/Dim, K=Index2%Dim, Pos=Find(I, J), Row=I, Col;
value=0;
if (Pos==DWORD(-1)) return false;
Col=L*Links[I].Size()*Dim+Find(I, J)*Dim+K;
value=Array[Row][Col];
return true;
}
void Mul(RVector&, RVector&);
double Mul(DWORD, RVector&);
void write(ofstream&);
void read(ifstream&);
};
class RMatrix
{
private:
Vector Buffer;
DWORD size;
public:
RMatrix(DWORD sz)
{
size=sz;
Buffer.ReSize(size*(size+1)*0.5);
}
~RMatrix() {}
DWORD Size(void) { return size; }
double& Get(DWORD i, DWORD j) { return Buffer[(2*size+1-i)*0.5*i+j-i]; }
};
void RVector::Sub(RVector &Right)
{
for (DWORD i=0; i
(*this)[i]-=Right[i];
}
void RVector::Add(RVector &Right)
{
for (DWORD i=0; i
(*this)[i]+=Right[i];
}
void RVector::Mul(double koff)
{
for (DWORD i=0; i
(*this)[i]*=koff;
}
void RVector::Sub(RVector &Right, double koff)
{
for (DWORD i=0; i
(*this)[i]-=Right[i]*koff;
}
TSMatrix::TSMatrix(Vector * links, DWORD size, int dim)
{
Dim=dim;
Links=links;
Size=size;
Right.ReSize(Dim*Size);
Array=new Vector[Size];
for (DWORD i=0; i
Array[i].ReSize(Links[i].Size()*Dim*Dim);
}
void TSMatrix::Add(Matrix &FEMatr, Vector &FE) продолжение
--PAGE_BREAK--
{
double Res;
DWORD RRow;
for (DWORD i=0L; i
for (DWORD l=0L; l
for (DWORD j=0L; j
for (DWORD k=0L; k
{
Res=FEMatr[i*Dim+l][j*Dim+k];
if (Res) Add(FE[i], l, FE[j], k, Res);
}
for (DWORD i=0L; i
for (DWORD l=0L; l
{
RRow=FE[INT(i%(FE.Size()))]*Dim+l;
Res=FEMatr[i*Dim+l][FEMatr.Size1()];
if (Res) Add(RRow,Res);
}
}
DWORD TSMatrix::Find(DWORD I, DWORD J)
{
DWORD i;
for (i=0; i
if (Links[I][i]==J) return i;
return DWORD(-1);
}
void TSMatrix::Restore(Matrix &Matr)
{
DWORD i, j, NRow, NPoint, NLink, Pos;
Matr.ReSize(Size*Dim, Size*Dim+1);
for (i=0; i
for (j=0; j
{
NRow=j/(Array[i].Size()/Dim);
NPoint=(j-NRow*(Array[i].Size()/Dim))/Dim;
NLink=j%Dim;
Pos=Links[i][NPoint];
Matr[i*Dim+NRow][Pos*Dim+NLink]=Array[i][j];
}
for (i=0; i
Matr[i][Matr.Size1()]=Right[i];
}
void TSMatrix::Set(DWORD Index, DWORD Position, double Value, bool Case)
{
DWORD Row=Index, Col=Position*Links[Index].Size()*Dim+Find(Index, Index)*Dim+Position, i;
double koff=Array[Row][Col], val;
if (!Case) Right[Dim*Index+Position]=Value;
else
{
Right[Index*Dim+Position]=Value*koff;
for (i=0L; i
if (i!=Index*Dim+Position)
{
Set(Index*Dim+Position, i, 0);
Set(i, Index*Dim+Position, 0);
if (Get(i, Index*Dim+Position, val)
Right[i]-=val*Value;
}
}
}
void TSMatrix::Mul(RVector &Arr, RVector &Res)
{
DWORD i, j, NRow, NPoint, NLink, Pos;
Res.ReSize(Arr.Size());
for (i=0; i
for (j=0; j
{
NRow=j/(Array[i].Size()/Dim);
NPoint=(j-NRow*(Array[i].Size()/Dim))/Dim;
NLink=j%Dim;
Pos=Links[i][NPoint];
Res[i*Dim+NRow]+=Arr[Pos*Dim+NLink]*Array[i][j];
}
}
double TSMatrix::Mul(DWORD Index, RVector &Arr)
{
DWORD j, I=Index/Dim, L=Index%Dim, Start=L*(Array[I].Size()/Dim), Stop=Start+(Array[I].Size()/Dim), NRow, NPoint, NLink, Pos;
double Res=0;
for (j=Start; j
{
NRow=j/(Array[I].Size()/Dim);
NPoint=(j-NRow*(Array[I].Size()/Dim))/Dim;
NLink=j%Dim;
Pos=Links[I][NPoint];
Res+Arr[Pos*Dim+NLink]*Array[I][j];
}
return Res;
}
void TSMatrix::write(ofstream& Out)
{
DWORD ColSize;
Out.write((char *)&(Dim), sizeof(DWORD));
Out.write((char *)&(Size), sizeof(DWORD));
for (DWORD i=0; i
{
ColSize=Array[i].Size();
Out.write((char *)&(ColSize), sizeof(DWORD));
for (DWORD j=0; j
Out.write((char *)&(Array[i][j]), sizeof(double));
}
for (DWORD i=0; i
Out.write((char *)&(Right[i]), sizeof(double));
}
void TSMatrix::read(ifstream& In)
{
DWORD ColSize;
In.read((char *)&(Dim), sizeof(DWORD));
In.read((char *)&(Size), sizeof(DWORD));
if (Array) delete [] Array;
Array=new Vector[Size];
Right.ReSize(Size*Dim);
for (DWORD i=0; i
{
In.read((char *)&(ColSize), sizeof(DWORD));
Array[i].ReSize(ColSize);
for (DWORD j=0; j
In.read((char *)&(Array[i][j]), sizeof(double));
}
for (DWORD i=0; i
In.read((char *)&(Right[i]), sizeof(double));
}
bool Output(char * fname, Vector &x, Vector &y, Vector &z, Matrix &tr, DWORD n, DWORD NumNewPoints, DWORD ntr, Matrix &Bounds, DWORD CountBn) продолжение
--PAGE_BREAK--
{
char * Label=«NTRout»;
int type=CurrentType, type1=(type==BASE3D_4 || type==BASE3D_10)? 3: 4;
DWORD NewSize, i, j;
ofstream Out;
if (type==BASE3D_4) type1=3;
else
if (type==BASE3D_8) type1=4;
else
if (type==BASE3D_10) type1=6;
Out.open(fname, ios::out | ios::binary);
if (Out.bad()) return true;
Out.write((const char *) Label, 6*sizeof(char));
if (Out.fail()) return true;
Out.write((const char *) &type, sizeof(int));
if (Out.fail()) return true;
Out.write((const char *) &CountBn, sizeof(DWORD));
if (Out.fail())
{
Out.close();
return true;
}
Out.write((const char *) &(NewSize=n+NumNewPoints), sizeof(DWORD));
if (Out.fail()) return true;
Out.write((const char *) &(NumNewPoints), sizeof(DWORD));
if (Out.fail())
{
Out.close();
return true;
}
for (DWORD i=0; i
{
Out.write((const char *) &x[i], sizeof(double));
Out.write((const char *) &y[i], sizeof(double));
Out.write((const char *) &z[i], sizeof(double));
if (Out.fail())
{
Out.close();
return true;
}
}
for (i=0; i
{
Out.write((const char *) &x[n+i], sizeof(double));
Out.write((const char *) &y[n+i], sizeof(double));
if (Out.fail())
{
Out.close();
return true;
}
}
Out.write((const char *) &(ntr), sizeof(DWORD));
if (Out.fail())
{
Out.close();
return true;
}
for (i=0; i
for (j=0; j
{
DWORD out=tr[i][j];
Out.write((const char *) &out, sizeof(DWORD));
if (Out.fail())
{
Out.close();
return true;
}
}
for (i=0; i
for (j=0; j
{
DWORD out=Bounds[i][j];
Out.write((const char *) &out, sizeof(DWORD));
if (Out.fail())
{
Out.close();
return true;
}
}
}
bool Test(DWORD * a, DWORD * b)
{
bool result;
int NumPoints=3;
if (CurrentType==BASE3D_8) NumPoints=4;
else
if (CurrentType==BASE3D_10) NumPoints=6;
for (int i=0; i
{
result=false;
for (int j=0; j
if (b[j]==a[i])
{
result=true;
break;
}
if (result==false) return false;
}
return true;
}
void Convert(Vector &X, Vector &Y, Vector &Z, Matrix &FE, DWORD NumTr, Matrix &Bounds, DWORD &BnCount)
{
int cData8[6][5]={{0, 4, 5, 1, 7}, {6, 2, 3, 7, 0}, {4, 6, 7, 5, 0}, {2, 0, 1, 3, 5}, {1, 5, 7, 3, 4}, {6, 4, 0, 2, 1}}, cData4[4][4]={{0, 1, 2, 3}, {1, 3, 2, 0}, {3, 0, 2, 1}, {0, 3, 1, 2}}, cData10[4][7]={{0, 1, 2, 4, 5, 6, 3}, {0, 1, 3, 4, 8, 7, 2}, {1, 3, 2, 8, 9, 5, 0}, {0, 2, 3, 6, 9, 7, 1}}, cData[6][7], Data[6], l, Num1, Num2, m;
DWORD i, j, p[6], pp[6], Index;
Matrix BoundList(4*NumTr, 6);
double cx, cy, cz, x1, y1, z1, x2, y2, z2, x3, y3, z3;
Bounds.ReSize(4*NumTr, 6);
switch (CurrentType)
{
case BASE3D_4:
Num1=4;
Num2=3;
for (l=0; l
for (m=0; m
break;
case BASE3D_8:
Num1=6;
Num2=4;
for (l=0; l
for (m=0; m
break;
case BASE3D_10:
Num1=4;
Num2=6; продолжение
--PAGE_BREAK--
for (l=0; l
for (m=0; m
}
printf(«Create bounds...\r»);
for (i=0; i
for (int j=0; j
if (!BoundList[i][j])
{
for (l=0; l
for (DWORD k=i+1; k
for (int m=0; m
if (!BoundList[k][m])
{
for (int l=0; l
pp[l]=FE[k][cData[m][l]];
if (Test(p, pp))
BoundList[i][j]=BoundList[k][m]=1;
}
}
x1=X[FE[i][cData[j][0]]];
y1=Y[FE[i][cData[j][0]]];
z1=Z[FE[i][cData[j][0]]];
x2=X[FE[i][cData[j][1]]];
y2=Y[FE[i][cData[j][1]]];
z2=Z[FE[i][cData[j][1]]];
x3=X[FE[i][cData[j][2]]];
y3=Y[FE[i][cData[j][2]]];
z3=Z[FE[i][cData[j][2]]];
for (l=0; l
if (((cx-x1)*(y2-y1)*(z3-z1)+(cy-y1)*(z2-z1)*(x3-x1)+(y3-y1)*(cz-z1)*(x2-x1)-(x3-x1)*(y2-y1)*(cz-z1)-(y3-y1)*(z2-z1)*(cx-x1)-(cy-y1)*(z3-z1)*(x2-x1))>0)
{
if (CurrentType==BASE3D_4)
{
Data[0]=cData[j][0];
Data[1]=cData[j][2];
Data[2]=cData[j][1];
}
else
if (CurrentType==BASE3D_10)
{
Data[0]=cData[j][0];
Data[1]=cData[j][2];
Data[2]=cData[j][1];
Data[3]=cData[j][5];
Data[5]=cData[j][3];
}
else
{
Data[0]=cData[j][0];
Data[1]=cData[j][3];
Data[2]=cData[j][2];
Data[3]=cData[j][1];
}
}
for (l=0; l
BnCount++;
}
void main(int argc,char * argv)
{
char * input1, * input2, * input3, * op="", * sw;
if (argc6) return;
sw=argv[1];
input1=argv[2];
input2=argv[3];
input3=argv[4];
if (!strcmp(sw, "-t10")) CurrentType=BASE3D_10;
else
if (!strcmp(sw, "-c8")) CurrentType=BASE3D_8;
else
{
printf(«Unknown switch %s\n\n», sw);
return;
}
if (argc==6)
{
op=argv[5];
if (strcmp(op, "/8") && strcmp(op, "/6"))
{
printf(«Unknown options %s\n\n», op);
return;
}
}
if (CreateFile(input1, input2, input3, op)) printf(«OK\n»);
}
bool CreateFile(char * fn1, char * fn2, char * fn3, char * Op)
{
FILE * in1, * in2, * in3;
Vector X(1000), Y(1000), Z(1000);
DWORD NumPoints, NumFE, NumBounds=0, tmp;
Matrix FE(1000, 10), Bounds;
if ((in1=fopen(fn1, «r»))==NULL)
{
printf(«Unable open file %s», fn1);
return false;
}
if ((in2=fopen(fn2, «r»))==NULL)
{
printf(«Unable open file %s», fn2);
return false;
}
if (CurrentType==BASE3D_10)
{
if (!ReadTetraedrData(fn1, fn2, in1, in2, X, Y, Z, FE, NumPoints, NumFE)) return false;
if (!strcmp(Op, "/8")) Convert1024(FE, NumFE);
Convert(X, Y, Z, FE, NumFE, Bounds, NumBounds);
return !Output(fn3, X, Y, Z, FE, NumPoints, 0, NumFE, Bounds, NumBounds);
}
if (CurrentType==BASE3D_8)
{
if (!ReadCubeData(fn1, fn2, in1, in2, X, Y, Z, FE, NumPoints, NumFE)) return false;
if (!strcmp(Op, "/6")) Convert824(FE, NumFE);
Convert(X, Y, Z, FE, NumFE, Bounds, NumBounds);
return !Output(fn3, X, Y, Z, FE, NumPoints, 0, NumFE, Bounds, NumBounds);
}
return false;
}
void Convert824(Matrix &FE, DWORD &NumFE)
{
Matrix nFE(6*NumFE, 4);
DWORD data[][4]={{0, 2, 3, 6}, {4, 5, 1, 7}, {0, 4, 1, 3}, {6, 7, 3, 4}, {1, 3, 7, 4}, {0, 4, 6, 3}}, Current=0;
for (DWORD i=0; i продолжение
--PAGE_BREAK--
for (DWORD j=0; j
{
for (DWORD k=0; k
nFE[Current][k]=FE[i][data[j][k]];
Current++;
}
CurrentType=BASE3D_4;
NumFE=Current;
FE=nFE;
}
void Convert1024(Matrix &FE, DWORD &NumFE)
{
Matrix nFE(8*NumFE, 4);
DWORD data[][4]={{3, 7, 8, 9}, {0, 4, 7, 6}, {2, 5, 9, 6}, {7, 9, 8, 6}, {4, 8, 5, 1}, {4, 5, 8, 6}, {7, 8, 4, 6}, {8, 9, 5, 6}}, Current=0;
for (DWORD i=0; i
for (DWORD j=0; j
{
for (DWORD k=0; k
nFE[Current][k]=FE[i][data[j][k]];
Current++;
}
CurrentType=BASE3D_4;
NumFE=Current;
FE=nFE;
}
bool ReadTetraedrData(char * fn1, char * fn2, FILE * in1, FILE * in2, Vector &X, Vector &Y, Vector &Z, Matrix &FE, DWORD &NumPoints, DWORD &NumFE)
{
double tx, ty, tz;
char TextBuffer[1001];
DWORD Current=0L, tmp;
while (!feof(in1))
{
if (fgets(TextBuffer, 1000, in1)==NULL)
{
if (feof(in1)) break;
printf(«Unable read file %s», fn1);
fclose(in1);
fclose(in2);
return false;
}
if (sscanf(TextBuffer, "%ld %lf %lf %lf", &NumPoints, &tx, &ty, &tz)!=4) continue;
X[Current]=tx;
Y[Current]=ty;
Z[Current]=tz;
if (++Current==999)
{
Vector t1=X, t2=Y, t3=Z;
X.ReSize(2*X.Size());
Y.ReSize(2*X.Size());
Z.ReSize(2*X.Size());
for (DWORD i=0; i
{
X[i]=t1[i];
Y[i]=t2[i];
Z[i]=t3[i];
}
}
if (Current%100==0) printf(«Line: %ld\r», Current);
}
fclose(in1);
NumPoints=Current;
Current=0L;
while (!feof(in2))
{
if (fgets(TextBuffer, 1000, in2)==NULL)
{
if (feof(in2)) break;
printf(«Unable read file %s», fn2);
fclose(in2);
return false;
}
if (sscanf(TextBuffer, "%d %d %d %d %d %ld %ld %ld %ld %ld %ld %ld %ld", &tmp, &tmp, &tmp, &tmp, &tmp, &FE[Current][0], &FE[Current][1], &FE[Current][2], &FE[Current][3], &FE[Current][4], &FE[Current][5], &FE[Current][6], &FE[Current][7])!=13) continue;
if (fgets(TextBuffer, 1000, in2)==NULL)
{
printf(«Unable read file %s», fn2);
fclose(in2);
return false;
}
if (sscanf(TextBuffer, "%ld %ld", &FE[Current][8], &FE[Current][9])!=2)
{
printf(«Unable read file %s», fn2);
fclose(in2);
return false;
}
}
}
bool ReadCubeData(char * fn1, char * fn2, FILE * in1, FILE * in2, Vector &X, Vector &Y, Vector &Z, Matrix &FE, DWORD &NumPoints, DWORD &NumFE)
{
double tx, ty, tz;
char TextBuffer[1001];
DWORD Current=0L, tmp;
while (!feof(in1))
{
if (fgets(TextBuffer, 1000, in1)==NULL)
{
if (feof(in1)) break;
printf(«Unable read file %s», fn1);
fclose(in1);
fclose(in2);
return false;
}
if (sscanf(TextBuffer, "%ld %lf %lf %lf", &NumPoints, &tx, &ty, &tz)!=4) continue;
X[Current]=tx;
Y[Current]=ty;
Z[Current]=tz;
if (++Current==999)
{
Vector t1=X, t2=Y, t3=Z;
X.ReSize(2*X.Size());
Y.ReSize(2*X.Size());
Z.ReSize(2*X.Size());
for (DWORD i=0; i
{
X[i]=t1[i];
Y[i]=t2[i];
Z[i]=t3[i];
}
}
if (Current%100==0) printf(«Line: %ld\r», Current);
}
fclose(in1);
NumPoints=Current;
Current=0L;
while (!feof(in2))
{
if (fgets(TextBuffer, 1000, in2)==NULL)
{
if (feof(in2)) break;
printf(«Unable read file %s», fn2);
fclose(in2);
return false;
}
if (sscanf(TextBuffer, "%d %d %d %d %d %ld %ld %ld %ld %ld %ld %ld %ld", &tmp, &tmp, &tmp, &tmp, &tmp, &FE[Current][0], &FE[Current][1], &FE[Current][3], &FE[Current][2], &FE[Current][4], &FE[Current][5], &FE[Current][7], &FE[Current][6])!=13) continue;
if (++Current==999)
{
Matrix t=FE;
FE.ReSize(2*FE.Size1(), 10);
for (DWORD i=0; i
for (DWORD j=0; j
}
if (Current%100==0) printf(«Line: %ld\r», Current);
}
NumFE=Current;
for (DWORD i=0; i
for (DWORD j=0; j
return true;
}