ЮК "ОСНОВНОЙ ЗАКОН"

г. Киев, бул. Пушкина, 2а
тел.: (044) 334-99-77
   (095) 407-407-3
         (096) 703-11-82

график работы: пн.- пт. с 9:00 до 18:00

Рассматривается вопрос о предоставление нотариусам права выдачи извлечения из Реестра прав на недвижимое имущество.
Министерством юстиции был разработан проект Закона «О внесении изменений в некоторые Законы Украины относительно предоставления информации о государст...

Держреєстрація речових прав на нерухоме майно та їх обтяжень у 2014 році буде здійснюватись за новою - удосконаленою та спрощеною - процедурою.
Постанова Кабінету Міністрів "Про затвердження порядку державної реєстрації прав на нерухоме майно та їх обтяжень і Порядку надання інформації з Держа...

Наукова Мережа >> Лінійна алгебра: від Гаусса до суперкомп'ютерів майбутнього

Лінійна алгебра: від Гаусса до суперкомп'ютерів майбутнього В.П.Ільін,доктор фізико-математичних наук,професор,...
Введення: історія, передумови та проблеми
Зовсім алгебраїчна, але дуже плідна ідея

Лінійна алгебра: від Гаусса до суперкомп'ютерів майбутнього В.П.Ільін,доктор фізико-математичних наук,професор,
головний науковий співробітник Інституту обчислювальної математики і математичної геофізкі СО РАН.
Опубліковано в журналі "Природа" , N 6, 1999 г. зміст

про автора

Валерій Павлович Ільїн

, Доктор фізико-математичних наук, професор, головний науковий співробітник Інституту обчислювальної математики і математичної геофізкі СО РАН. Область наукових інтересів - обчислювальна математика , інформатика , математичне моделювання . Автор понад 250 наукових статей і дев'яти монографій (частина з них написана в співавторстві).

... Повірив
Я алгеброю гармонію
А. С. Пушкін

Введення: історія, передумови та проблеми

Завдання чисельного рішення систем лінійних алгебраїчних рівнянь (СЛАР) має незапам'ятну історію. класичний метод виключення , Активно розвивається і досліджуваний навіть в наші дні, був відкритий К. Гаусом в 1849 р Однак ще за 2000 років до цього в Стародавньому Китаї видані "Дев'ять книг про математичному мистецтві" , Де цей алгоритм вже викладено в характерній для свого часу "натуральної" формі, але фактично з використанням матричних перетворень.

Аж до початку XX в. алгебра залишалася "наукою про рішення рівнянь", після чого відбулося її поділ на вищу алгебру (операції з абстрактними об'єктами різної природи) і лінійну , Основа якої - матричне числення .

Становлення сучасних обчислювальних методів лінійної алгебри можна вважати таким, що відбувся після виходу в 1960 р книги Д.К. і В.Н. Фаддєєва з однойменною назвою, по якій навчалося не одне покоління російських і зарубіжних математиків. Необхідно підкреслити, що актуальні проблеми обчислювальної алгебри мають фундаментальний характер не тільки тому, що поточна комп'ютеризація різних областей знань в значній мірі зводиться до векторно-матричних процедурам. вивчення матриць , є операторами в найпростіших скінченновимірних просторах , Дозволяє виявити найбільш глибокі і тонкі властивості математичних об'eктов, що мають своє значення для функціонального аналізу , теорії апроксимації , диференціальних рівнянь і так далі

Протягом останніх десятиліть ознаменовані бурхливим розвитком чисельних методів , Що знайшли відображення в книгах Г. І. Марчука , А.А.Самарского , С.К.Годунова , Дж.Голуба , О.Аксельсона та інших. В рамках ітераційних методів розв'язання СЛАР значні просування досягнуті в таких сучасних напрямах, як алгоритми пов'язаних напрямків , Послідовної і симетричною верхньої релаксації, неявні алгоритми змінних напрямків і методи неповної факторизації.

Незважаючи на наявні в цій галузі теоретичні досягнення, а також на бурхливе зростання світових обчислювальних потужностей, проблема конструювання та дослідження нових швидких алгоритмів розв'язання СЛАР не втрачає своєї актуальності, і потік публікацій з цієї тематики тільки збільшується. Справа пояснюється тим, що виникають практичні завдання поряд з ускладненням обчислювальних процедур вимагають від методів вирішення все більшої точності і надійності. Як то кажуть, апетит приходить під час їжі, і з цим пов'язаний той унікальний феномен, що, незважаючи на появу все нових поколінь ЕОМ, за останні 50 років рішення "великих" (на поточний момент) завдань завжди займало приблизно однакове астрономічний час.

Образно кажучи, можна сформулювати теорему про існування перманентного дефіциту машинних ресурсів, стимулюючого як подальше нарощування комп'ютерних потужностей, так і розвиток нових супералгорітмов.

Головне джерело надвеликих СЛАР - сіткові методи (Кінцевих різниць, кінцевих обсягів і кінцевих елементів) рішення багатовимірних крайових задач, що виникають при моделюванні процесів або явищ. Для оцінки потреб обчислювальних ресурсів розглянемо сітковий тривимірну розрахункову область у формі паралелепіпеда , утворену координатними лініями
Головне джерело надвеликих СЛАР - сіткові методи (Кінцевих різниць, кінцевих обсягів і кінцевих елементів) рішення багатовимірних крайових задач, що виникають при моделюванні процесів або явищ Якщо ми вирішуємо одне диференціальне рівняння другого порядку еліптичного типу (наприклад, рівняння стаціонарної дифузії або теплопровідності ), То в результаті його найпростішої апроксимації для кожного вузла (i, j, k) виходить рівняння виду

де коефіцієнти де коефіцієнти виражаються через кроки сітки і параметри вихідної задачі виражаються через кроки сітки і параметри вихідної задачі. Такий системі рівнянь відповідає квадратна матриця А порядку IJK з числом ненульових елементів на кожному рядку не більше 7.

Нехай заради простоти . Тоді для реалізації методу виключення Гауса потрібно виконати приблизно арифметичних операцій і запам'ятати проміжних чисел. На сьогодні завдання середньої складності відповідає K = 100, що призводить до значень і . На повсякденній мові це означає близько трьох годин роботи комп'ютера швидкодією 10 гігафлоп, тобто "флоп" - арифметичних операцій над "нормальними" речовими числами в секунду, при наявності оперативної пам'яті близько 10 гігабайт. Це набагато перевершує ресурси персональних комп'ютерів і робочих станцій, але на світовому ринку така ЕОМ - середнього класу. Однак якщо перейти до "великої" завданню з K = 1000, то вона вже виявляється міцним горішком навіть для рекордного суперкомп'ютера зі швидкістю в один терафлоп ( ) І пам'яттю в один терабайт.

Двовимірні завдання набагато легше. Однак і вони вимагають величезних ресурсів, якщо потрібно знаходити оптимальні параметри потрібних рішень (щоб задовольнити поставленим обмеженням і обраними критеріями якості), розраховувати тривалі за часом або, навпаки, швидкоплинні процеси, враховувати сільнонелінейние ефекти. Це призводить до багаторазового вирішення проміжних лінійних систем. Важливо відзначити, що це - найбільш трудомістка частина великомасштабного обчислювального експерименту, так як інші розрахункові етапи вимагають обсягу арифметичних дій, пропорційного загальної кількості вузлів сітки.

Кардинальне засіб підвищення продуктивності комп'ютерів (за професійними прогнозами - до петафлопного швидкодії, тобто до операцій в секунду до 2015 г.) - створення багатопроцесорних обчислювальних систем (до або процесорів). Звідси однією з перших за актуальності проблем в обчислювальної алгебри стає розпаралелювання алгоритмів і їх відображення на архітектуру багатопроцесорних ЕОМ. Нагальність цього питання, в тому числі при вирішенні СЛАР, виникає з того загальновідомого факту, що ефективність завантаження всіх пристроїв - це хворе місце різних суперкомп'ютерів, і реалізація алгоритмів без урахування, наприклад, комунікаційних втрат може знизити фактичну продуктивність багатопроцесорної системи до декількох відсотків від її паспортних даних. Один з найефективніших методів вирішення СЛАР високого порядку базується на ітераційних алгоритмах неповної факторизації, які отримали зараз саме широке поширення в світовій обчислювальної практиці 1 . Дана стаття являє останні результати автора, що стосуються нових, перспективних підходів: узагальненого принципу компенсації в наближеною матричної факторизації , Адаптивних ітераційних методів з оптимальними впорядкованість і, нарешті, проблеми розпаралелювання алгоритмів на основі декомпозиції областей.

Зовсім алгебраїчна, але дуже плідна ідея

Ідея методу неповної факторизації для вирішення алгебри

полягає в побудові такої матриці B, званої предобусловлівающей, яка легко б зверталася і була б близькою до вихідної матриці A в тому сенсі, що власні числа матриці-твори B-1A не сильно різняться між собою. Тоді послідовні наближення un будуються за допомогою ітераційного процесу , Який в канонічній записи має наступний вигляд: Тут полягає в побудові такої матриці B, званої предобусловлівающей, яка легко б зверталася і була б близькою до вихідної матриці A в тому сенсі, що власні числа матриці-твори B-1A не сильно різняться між собою - обчислювані параметри, а число ітерацій для досягнення необхідної точності залежить від ставлення
,
званого числом обумовленості матриці B-1A. Ця величина k виявляється магічним числом в лінійної алгебри, характеризуючи головні обчислювальні якості будь-якої матриці, в тому числі чутливість до погрішностей заокруглень .

вводячи позначення
вводячи позначення , для векторів корекції і невязки, співвідношення (3) можна розбити на два: , , з яких видно, що найбільш трудомістка процедура на кожній ітерації - рішення допоміжної системи з матрицею B (звичайно, якщо остання не дуже тривіальна) ,
для векторів корекції і невязки, співвідношення (3) можна розбити на два:
, ,
з яких видно, що найбільш трудомістка процедура на кожній ітерації - рішення допоміжної системи з матрицею B (звичайно, якщо остання не дуже тривіальна). Першовідкривач методів неповної факторизації Н.І.Булеев запропонував (середина 50-х років, закритий ядерний центр в г.Обнінск) шукати B як наближену (неповну) факторизацию вихідної матриці A:

де L, U - легко обчислюються (набагато простіше, ніж в точної факторизації) і легко оборотні нижня і верхня трикутні матриці .

Геніальне все просто: крім конструктивного побудови множників L, U, Булєєв запропонував критерієм близькості матриць вимога

де e - вектор з постійними (одиничними) компонентами; він назвав його принципом компенсації . Ця зовсім алгебраїчна ідея виходила з тих сермяжное міркувань, що в задачах матфізікі рішення в основному гладкі, а тоді за умови (5) на кожній ітерації "зайві" члени (обумовлені неточністю факторизации (4)) будуть взаємно компенсуватися.

Нові методи на багатьох практичних завданнях виявляли приголомшливе швидкодію, але часом не все було гладко. Це говорило про необхідність більш глибокого вивчення нового класу алгоритмів, теорії яких тоді не було. Але, як відомо, немає пророка в своїй вітчизні - провідні фахівці в СРСР ідею неповної факторизації не підхопив, продовжуючи захоплено розвивати інші (які прийшли з-за кордону) модні напрями.

На Заході ж методи Булєєва були кілька разів перевідкриття і стали активно вдосконалюватися. Зокрема, евристичне умова (5), яке на алгебраїчному мовою не що інше, як принцип узгодження малих сум матриць B і A, було пояснено і ефективно використано в поєднанні з прискоренням ітерацій універсальними методами сполучених градієнтів . Вражаючий збіг, але практично одночасно (в 1983 р) і незалежно в роботах автора з О.Аксельсоном (Голландія) і Дж.Голуба (США) з колегами були запропоновані неявні (блокові) методи неповної факторизації, в яких матричні множники L, U - суть блочно-трикутні матриці, причому діагональні блоки - стрічкові матриці , Ненульові елементи яких зосереджені тільки в околиці стрічки заданої ширини d близько головній діагоналі . Такі алгоритми дозволили уточнити саму наближену факторизацию і значно скоротити число ітерацій. Однак тут виникла нова нетрадиційна завдання обчислювальної алгебри: знайти стрічкову частина матриці, оберненої до стрічкової ж матриці. Для цього завдання вдалося знайти витончене рішення (природно, трудомісткість процедури збільшується з ростом ширини стрічки d).

У цьому місці закладена принципова методологічна проблема, яка чекає досі свого рішення. Нехай, наприклад, C - невироджених матриця . Якщо ми обчислюємо стрічкову частина ширини У цьому місці закладена принципова методологічна проблема, яка чекає досі свого рішення від оберненої матриці - позначимо її через , - то знаходимо в певному сенсі наближення до зворотного матриці (Яка в загальному випадку щільна, тобто не містить нулів). Дійсно, якщо d збільшується аж до порядку матриці N, то При d = N матрична апроксимація стає точної і метод вирішення СЛАР з ітераційного перетворюється в прямий, що дає точне рішення за кінцеве число дій. Фактично в цьому випадку метод наближеної факторизації переходить в блоковий метод Гаусса, який для сіткових систем рівнянь занадто дорогий.

Тут і виникає питання: яка оптимальна ширина стрічкової апроксимації оберненої матриці , Щоб забезпечити підсумкову ефективність итерационного методу? Або, іншими словами, досягти заданої точності за мінімальне число арифметичних дій? Зрозуміло, що краще - ворог хорошого, і в повному обсязі рішення проблеми оптимізації алгоритмів - це недосяжна блакитна мрія, до якої треба прагнути, але тільки дробовими кроками, розширюючи життєвий простір конкретними результатами для окремих типів систем.

1 Il'in VP Iterative incomplete factorization methods.Singapore, 1992;Ільїн В.П.Методи неповної факторизації для вирішення алгебраїчних систем.М., 1995.

назад | вперед

написати коментар
Або, іншими словами, досягти заданої точності за мінімальне число арифметичних дій?

Cистема управления сайта от студии «АртДизайн»