Неполная столбцово-строчная факторизация матриц для итерационного решения больших систем уравнений
Для формирования предобусловливателей предложен метод неполной столбцово-строчной (ICR) факторизации несимметричных матриц. Метод не требует перестановок строк и столбцов в субматрицах. Получаемые факторные матрицы не являются треугольными. Оригинальная процедура поиска ведущего элемента в субматриц...
Gespeichert in:
| Veröffentlicht in: | Электронное моделирование |
|---|---|
| Datum: | 2010 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2010
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/61684 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Неполная столбцово-строчная факторизация матриц для итерационного решения больших систем уравнений / С.Е. Саух // Электронное моделирование. — 2010. — Т. 32, № 6. — С. 3-14. — Бібліогр.: 7назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860248991307923456 |
|---|---|
| author | Саух, С.Е. |
| author_facet | Саух, С.Е. |
| citation_txt | Неполная столбцово-строчная факторизация матриц для итерационного решения больших систем уравнений / С.Е. Саух // Электронное моделирование. — 2010. — Т. 32, № 6. — С. 3-14. — Бібліогр.: 7назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | Для формирования предобусловливателей предложен метод неполной столбцово-строчной (ICR) факторизации несимметричных матриц. Метод не требует перестановок строк и столбцов в субматрицах. Получаемые факторные матрицы не являются треугольными. Оригинальная процедура поиска ведущего элемента в субматрице по критерию минимума расхождения по норме Фробениуса между преобразуемой и преобразованной субматрицами обеспечивает устойчивость вычислений для плохо обусловленных матриц. В методе ICR-факторизации применена оригинальная оценка значимости элементов факторных матриц, основанная на сопоставлении норм строк и столбцов преобразуемых и вычитаемых субматриц. Приведены примеры решения тестовых систем уравнений с использованием итерационных методов проекций решений на подпространства Крылова, подтверждающие преимущества предложеного метода.
Для формування передобумовлювачів запропоновано метод неповної стовпцево-рядкової (ICR) факторизації несиметричних матриць. Метод не потребує перестановок рядків і стовпців у субматрицях. Одержувані факторні матриці не є трикутними. Оригінальна процедура пошуку провідних елементів в субматрицях за критерієм мінімальної розбіжності по нормі Фробеніуса між перетворюваною і перетвореною субматрицями забезпечує стійкість обчислень для погано обумовлених матриць. У методі ICR-факторизації застосовано оригінальну оцінку значимості елементів факторних матриць, базовану на зіставленні норм рядків і стовпців перетворюваних субматриць та субматриць, що віднімаються. Наведено приклади розв’язку тестових систем рівнянь з використанням ітераційних методів проекцій розв’язків на підпростори Крилова, які підтверджують переваги запропонованого методу.
A method of the column-line (ICR) factorization of asymmetrical matrices is proposed for forming predeterminers. The method does not require permutation of lines and columns in submatrices. The obtained factor matrices are not triangular. The original procedure of the search for the leading element in the submatrix by the criterion of minimum of divergence by the Frobenius norm between the transformable and transformed submatrices provides for the stability of calculations for badly determined matrices. An original estimation of the value of the factor matrices elements is used in the method of ICR-factorization. The examples of solution for the test equation systems with the use of iterational methods of solution projections to Krylov’s subspaces are presented which confirm the advantages of the proposed method.
|
| first_indexed | 2025-12-07T18:40:38Z |
| format | Article |
| fulltext |
ÓÄÊ 519.612
Ñ. Å. Ñàóõ, ä-ð òåõí. íàóê
Èí-ò ïðîáëåì ìîäåëèðîâàíèÿ
â ýíåðãåòèêå èì.Ã.Å.Ïóõîâà ÍÀÍ Óêðàèíû
(Óêðàèíà, 03164, Êèåâ, óë. Ãåíåðàëà Íàóìîâà, 15,
òåë. (044) 4249164, E-mail:saukh@svitonline.com)
Íåïîëíàÿ ñòîëáöîâî-ñòðî÷íàÿ
ôàêòîðèçàöèÿ ìàòðèö äëÿ èòåðàöèîííîãî
ðåøåíèÿ áîëüøèõ ñèñòåì óðàâíåíèé
Äëÿ ôîðìèðîâàíèÿ ïðåäîáóñëîâëèâàòåëåé ïðåäëîæåí ìåòîä íåïîëíîé ñòîëáöîâî-ñòðî÷-
íîé (ICR) ôàêòîðèçàöèè íåñèììåòðè÷íûõ ìàòðèö. Ìåòîä íå òðåáóåò ïåðåñòàíîâîê ñòðîê è
ñòîëáöîâ â ñóáìàòðèöàõ. Ïîëó÷àåìûå ôàêòîðíûå ìàòðèöû íå ÿâëÿþòñÿ òðåóãîëüíûìè.
Îðèãèíàëüíàÿ ïðîöåäóðà ïîèñêà âåäóùåãî ýëåìåíòà â ñóáìàòðèöå ïî êðèòåðèþ ìèíèìóìà
ðàñõîæäåíèÿ ïî íîðìå Ôðîáåíèóñà ìåæäó ïðåîáðàçóåìîé è ïðåîáðàçîâàííîé ñóáìàò-
ðèöàìè îáåñïå÷èâàåò óñòîé÷èâîñòü âû÷èñëåíèé äëÿ ïëîõî îáóñëîâëåííûõ ìàòðèö. Â
ìåòîäå ICR-ôàêòîðèçàöèè ïðèìåíåíà îðèãèíàëüíàÿ îöåíêà çíà÷èìîñòè ýëåìåíòîâ ôàê-
òîðíûõ ìàòðèö, îñíîâàííàÿ íà ñîïîñòàâëåíèè íîðì ñòðîê è ñòîëáöîâ ïðåîáðàçóåìûõ è
âû÷èòàåìûõ ñóáìàòðèö. Ïðèâåäåíû ïðèìåðû ðåøåíèÿ òåñòîâûõ ñèñòåì óðàâíåíèé ñ
èñïîëüçîâàíèåì èòåðàöèîííûõ ìåòîäîâ ïðîåêöèé ðåøåíèé íà ïîäïðîñòðàíñòâà Êðûëîâà,
ïîäòâåðæäàþùèå ïðåèìóùåñòâà ïðåäëîæåíîãî ìåòîäà.
Äëÿ ôîðìóâàííÿ ïåðåäîáóìîâëþâà÷³â çàïðîïîíîâàíî ìåòîä íåïîâíî¿ ñòîâïöåâî-ðÿäêîâî¿
(ICR) ôàêòîðèçàö³¿ íåñèìåòðè÷íèõ ìàòðèöü. Ìåòîä íå ïîòðåáóº ïåðåñòàíîâîê ðÿäê³â ³
ñòîâïö³â ó ñóáìàòðèöÿõ. Îäåðæóâàí³ ôàêòîðí³ ìàòðèö³ íå º òðèêóòíèìè. Îðèã³íàëüíà
ïðîöåäóðà ïîøóêó ïðîâ³äíèõ åëåìåíò³â â ñóáìàòðèöÿõ çà êðèòåð³ºì ì³í³ìàëüíî¿ ðîçá³æ-
íîñò³ ïî íîðì³ Ôðîáåí³óñà ì³æ ïåðåòâîðþâàíîþ ³ ïåðåòâîðåíîþ ñóáìàòðèöÿìè çàáåçïå-
÷óº ñò³éê³ñòü îá÷èñëåíü äëÿ ïîãàíî îáóìîâëåíèõ ìàòðèöü. Ó ìåòîä³ ICR-ôàêòîðèçàö³¿
çàñòîñîâàíî îðèã³íàëüíó îö³íêó çíà÷èìîñò³ åëåìåíò³â ôàêòîðíèõ ìàòðèöü, áàçîâàíó íà
ç³ñòàâëåíí³ íîðì ðÿäê³â ³ ñòîâïö³â ïåðåòâîðþâàíèõ ñóáìàòðèöü òà ñóáìàòðèöü, ùî â³ä-
í³ìàþòüñÿ. Íàâåäåíî ïðèêëàäè ðîçâ’ÿçêó òåñòîâèõ ñèñòåì ð³âíÿíü ç âèêîðèñòàííÿì ³òåðà-
ö³éíèõ ìåòîä³â ïðîåêö³é ðîçâ’ÿçê³â íà ï³äïðîñòîðè Êðèëîâà, ÿê³ ï³äòâåðäæóþòü ïåðåâàãè
çàïðîïîíîâàíîãî ìåòîäó.
K ë þ ÷ å â û å ñ ë î â à: ðàçðåæåííûå ìàòðèöû, íåïîëíàÿ ôàêòîðèçàöèÿ, ïðåäîáóñëîâëèâà-
òåëü, âåäóùèå ýëåìåíòû, íåïîëíàÿ ñòîëáöîâî-ñòðî÷íàÿ ôàêòîðèçàöèÿ.
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 6 3
����������� ��
���
��
�
�
����
Ìåòîä CR-ôàêòîðèçàöèè ìàòðèö [1] îñíîâàí íà ïîñëåäîâàòåëüíîñòè
äåéñòâèé, âûïîëíÿåìûõ íàä çàäàííîé n n� ìàòðèöåé A â ñîîòâåòñòâèè ñ
ôîðìóëàìè
A Ai j j i( , )� � � �
1 1 1 1
C R ,
A ii j( , ) ( , :)� � �
1 1 1 0, A ji j( , ) (:, )� � �
1 1 1 0,
i n1 1 2�{ , , ..., }, j n1 1 2�{ , , ..., };
A Ai j i j j i( , ) ( , )� � � �� �
2 2 1 1 2 2
C R ,
A ii j( , ) ( ,:)� � �
2 2 2 0, A ji j( , ) (:, )� � �
2 2 2 0,
i n2 1 2�{ , , ..., }, i i2 1� , j n2 1 2�{ , , ..., }, j j2 1� ; (1)
. . . . . . . . . . . . . . . . . . . . . . . . . .
A Ai j i j j in n n n n n( , ) ( , )� � � �� � �
� �1 1
0C R ,
i nn �{ , , ..., }1 2 , i i k nn k� � �{ | , , ..., }1 2 1 ,
j nn �{ , , ..., }1 2 , j j k nn k� � �{ | , , ..., }1 2 1 .
Íàïðèìåð, â ðåçóëüòàòå ðàçëîæåíèÿ 6 6� ìàòðèöû A îòíîñèòåëüíî âòîðîé
ñòðîêè (i1 2� ) è ÷åòâåðòîãî ñòîëáöà ( j1 4� ) ïîëó÷àåì
A A
a a a a a a
a a a a a a
( , )� � � � �2 4 4 2
11 12 13 14 15 16
21 22 23 24 25
C R
26
31 32 33 34 35 36
41 42 43 44 45 46
51 52 53 54
a a a a a a
a a a a a a
a a a a a a
a a a a a a
55 56
61 62 63 64 65 66
�
� �c c c c c c r r r r r r
T
14 24 34 44 54 64 21 22 23 24 25 26
�
� � � � �a c r a c r a c r a c r a c r11 14 21 12 14 22 13 14 23 15 14 25 16 140 26
31 34 21 32 34 22 33 34 23 35 34 25
0 0 0 0 0 0
0a c r a c r a c r a c r a� � � � 36 34 26
41 44 21 42 44 22 43 44 23 45 44 250
�
� � � �
c r
a c r a c r a c r a c r a c r
a c r a c r a c r a c r
46 44 26
51 54 21 52 54 22 53 54 23 55 54 20
�
� � � � 5 56 54 26
61 64 21 62 64 22 63 64 23 65 640
a c r
a c r a c r a c r a c r
�
� � � � 25 66 64 26a c r�
,
ãäå ýëåìåíòû { | , , ..., }c ii 4 1 2 6� è { | , , ..., }r jj2 1 2 6� ñòîëáöà C4 è ñòðîêè R 2
ëåãêî îïðåäåëÿåì ïî ñîîòâåòñòâóþùèì ýëåìåíòàì èñõîäíîé ìàòðèöû A,
Ñ. Å. Ñàóõ
4 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 6
ïðè ýòîì ýëåìåíòû c24 è r24, óäîâëåòâîðÿþùèå ðàâåíñòâó c r a24 24 24� , íàõî-
äèì, ïðåäïîëàãàÿ, ÷òî c24 1� , è òîãäà r a24 24� ëèáî r24 1� , òîãäà c a24 24� .
Ïîñêîëüêó â ôîðìèðóåìûõ ìàòðèöàõ A i jk k( , )� � ñòîëáöû jk è ñòðîêè ik
ñòàíîâÿòñÿ íóëåâûìè, èòîãîâàÿ ìàòðèöà èìååò âèä A i jn n( , )� � �0. Èç ñîîòíî-
øåíèé (1) ñëåäóåò ðàâåíñòâî
A CR
k
n
j ik k
� �
�
1
C R ,
(2)
ãäå ìàòðèöû C è R ñîñòîÿò ñîîòâåòñòâåííî èç ñòîëáöîâ { | , , ..., }C j kk
j n�1 2
è ñòðîê{ | , , ..., }R i kk
i n�1 2 .
Ñîîòíîøåíèÿ (1) ÿâëÿþòñÿ îáîáùåíèåì èçâåñòíûõ ôîðìóë ôàêòîðè-
çàöèè. Óñòàíîâèâ çíà÷åíèÿ èíäåêñîâ ðàçëîæåíèÿ i kk � è j kk � , ïðèõîäèì
ê ôîðìóëàì LU-ôàêòîðèçàöèè, îïðåäåëÿþùèì íèæíå- è âåðõíåòðåóãîëü-
íóþ ôàêòîðíûå ìàòðèöû L C� èU R� . Åñëè â ñîîòíîøåíèÿ (1), (2) ââåñòè
ãðóïïîâûå èíäåêñû {ik } è { jk }, à òàêæå ñîîòâåòñòâóþùèå èì áëî÷íûå
ñòðîêè { }R i
T
k
è ñòîëáöû { }C jk
, òî ïîëó÷èì ôîðìóëû îáîáùåííîé áëî÷-
íîé ôàêòîðèçàöèè.  ÷àñòíîñòè, óñòàíîâèâ çíà÷åíèÿ ãðóïïîâûõ èíäåêñîâ
{ } { , }i k n kk � �
1 è { } { , }j k n kk � �
1 , ïîëó÷èì ôîðìóëû QI-ôàêòîðèçàöèè
[2], êîòîðûå îïðåäåëÿþò áëî÷íûå ñòðîêè R Rk n k
T
, �
1 è ñòîëáöû C Ck n k, �
1 .
Ââåäåíèå â (1), (2) ãðóïïîâûõ èíäåêñîâ ïåðåìåííîé ñòðóêòóðû var{ }ik è
var{ }jk , ïîçâîëÿåò îïðåäåëèòü ìåòîä ôàêòîðèçàöèè íå òîëüêî ñ ôèêñèðî-
âàííûìè, íî è ñ ïåðåìåííûìè ðàçìåðàìè áëî÷íûõ ñòðîê var{ }R i
T
k
è
ñòîëáöîâ var{ }C jk
.
Îñíîâíîå ïðåèìóùåñòâî ìåòîäà CR-ôàêòîðèçàöèè íàä ñóùåñòâóþ-
ùèìè ìåòîäàìè çàêëþ÷àåòñÿ â àäàïòèâíîñòè ñîîòíîøåíèé (1), (2) ê ïîçè-
öèîíèðîâàíèþ âûáèðàåìûõ âåäóùèõ ýëåìåíòîâ. Ñëåäóåò çàìåòèòü, ÷òî
èñïîëüçîâàíèå ñïåöèàëüíûõ ñõåì õðàíåíèÿ ðàçðåæåííûõ ìàòðèö ñîïðÿ-
æåíî ñ íåîáõîäèìîñòüþ âûïîëíåíèÿ ìíîæåñòâà íåàðèôìåòè÷åñêèõ îïåðà-
öèé äëÿ ïîëó÷åíèÿ äîñòóïà ê ìàòðè÷íûì ýëåìåíòàì. Ïîýòîìó îòñóòñòâèå â
ìåòîäå CR-ôàêòîðèçàöèè ïåðåñòàíîâîê ñòðîê è ñòîëáöîâ ïðèâîäèò ê ñîê-
ðàùåíèþ îáúåìà âû÷èñëåíèé ïðèáëèçèòåëüíî íà 1/3 [1].
Îäíàêî ïðèìåíåíèå ìåòîäà CR-ôàêòîðèçàöèè, êàê è äðóãèõ ìåòîäîâ
ðàçëîæåíèÿ ðàçðåæåííûõ ìàòðèö íà ìíîæèòåëè, ñîïðîâîæäàåòñÿ íåïðåä-
ñêàçóåìûì óâåëè÷åíèåì ÷èñëà íåíóëåâûõ ýëåìåíòîâ â ôàêòîðíûõ ìàòðè-
öàõ C è R îòíîñèòåëüíî èõ ÷èñëà â èñõîäíîé ìàòðèöå A.  óñëîâèÿõ æåñò-
êèõ îãðàíè÷åíèé âû÷èñëèòåëüíûõ ðåñóðñîâ íåïðåäñêàçóåìûå òðåáîâàíèÿ
ê îáúåìàì ïàìÿòè â ðÿäå ñëó÷àåâ íå ìîãóò áûòü óäîâëåòâîðåíû. Ïîýòîìó
ïðèáåãàþò ê ìåòîäàì íåïîëíîé CR-ôàêòîðèçàöèè (ICR-ôàêòîðèçàöèè) ìàò-
ðèö äëÿ ïîñòðîåíèÿ ïðåäîáóñëîâëèâàòåëåé A A CR�
�
~ ~~
� � ñ îøèáêîé �.
Íåïîëíàÿ ñòîëáöîâî-ñòðî÷íàÿ ôàêòîðèçàöèÿ ìàòðèö
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 6 5
Ôàêòîðèçîâàííûå ìàòðèöû-ïðåäîáóñëîâëåâàòåëè
~
A èñïîëüçóþòñÿ â
èòåðàöèîííûõ ìåòîäàõ ïðîåêöèé ðåøåíèé íà ïîäïðîñòðàíñòâà Êðûëîâà
äëÿ óñêîðåíèÿ ñõîäèìîñòè ïîñëåäîâàòåëüíîñòè ðåøåíèé ê òî÷íîìó ðåøå-
íèþ ñèñòåì àëãåáðàè÷åñêèõ óðàâíåíèé âèäà AX B� [3].
Îñîáåííîñòè ìåòîäîâ íåïîëíîé ôàêòîðèçàöèè ìàòðèö. Ñóùåñò-
âóþùèå ìåòîäû íåïîëíîé ôàêòîðèçàöèè ìàòðèö îñíîâàíû íà ðàçëè÷íûõ
ïîäõîäàõ ê îòáðàñûâàíèþ ÷àñòè íåíóëåâûõ ýëåìåíòîâ ôàêòîðíûõ ìàòðèö
[3—5].
Ëåãêî ðåàëèçóåìûì ÿâëÿåòñÿ ïîäõîä, ñîñòîÿùèé â ñîõðàíåíèè øàáëî-
íà P A ðàçìåùåíèÿ íåíóëåâûõ ýëåìåíòîâ èñõîäíîé ìàòðèöû A â øàá-
ëîíàõ P C
~
è P R
~
ðàçìåùåíèÿ íàèáîëåå çíà÷èìûõ ýëåìåíòîâ ìàòðèö
~
C è
~
R [3]. Ïðè òàêîì ïîäõîäå ñîáëþäàþòñÿ òðè óñëîâèÿ:
P C P A
~
� è P R P A
~
� ;
�( , )i j P A : [
~ ~
] [ ]C R Aij ij� ;
P A P� � �0.
Ââåäåííîå â ñëó÷àå L C� èU R� ïðèáëèæåííîå ïðåäñòàâëåíèå A L U�
~ ~
ÿâëÿåòñÿ íåïîëíîé LU-ôàêòîðèçàöèåé ìàòðèöû A èëè ILU(0)-ôàêòîðè-
çàöèåé ñ íóëåâûì çàïîëíåíèåì.  ñëó÷àå ðàñøèðåíèÿ øàáëîíà P L U
~ ~
îòíîñèòåëüíî øàáëîíà P A â ðåçóëüòàòå ó÷åòà p äîïîëíèòåëüíûõ íåíóëå-
âûõ ýëåìåíòîâ â êàæäîé ñòðîêå ìàòðèöû
~
U è â êàæäîì ñòîëáöå ìàòðèöû
~
L
âûïîëíÿåòñÿ ILU(p)-ôàêòîðèçàöèÿ. Äîñòîèíñòâîì ILU(p)-ôàêòîðèçàöèè,
ãäå p � 0, ÿâëÿåòñÿ ïðåäñêàçóåìîñòü òðåáîâàíèé ê îáúåìàì ïàìÿòè, íåîáõî-
äèìîé äëÿ ðàçìåùåíèÿ ôàêòîðíûõ ìàòðèö. Îäíàêî íåêîíòðîëèðóåìîå ïðî-
íèêíîâåíèå îøèáîê â ìàòðèöû
~
L è
~
U óõóäøàåò àïïðîêñèìàöèîííûå ñâîéñò-
âà ìàòðèöû-ïðåäóñëîâëèâàòåëÿ
~ ~ ~
A L U� , îñîáåííî â ñëó÷àÿõ ïëîõîé îáóñëîâ-
ëåííîñòè èñõîäíîé ìàòðèöû A. Ïîýòîìó ILU(p)-ôàêòîðèçàöèÿ èñïîëüçóåòñÿ â
àëãîðèòìàõ ðåøåíèÿ ñèñòåì óðàâíåíèé, íå èìåþùèõ îñîáåííîñòåé.
Áîëåå ñëîæåí â ðåàëèçàöèè ïîäõîä, îñíîâàííûé íà ðàçëè÷íûõ îöåíêàõ
çíà÷èìîñòè íåíóëåâûõ ýëåìåíòîâ ôàêòîðíûõ ìàòðèö L è U, ÷òî ïîçâîëÿåò
îãðàíè÷èòü âëèÿíèå îòáðàñûâàåìûõ ýëåìåíòîâ íà ïðîíèêíîâåíèå îøèáîê
â ìàòðèöó-ïðåäóñëîâëèâàòåëü âèäà A L U�
~ ~
.
 ñîâðåìåííûõ ìåòîäàõ íåïîëíîé LU-ôàêòîðèçàöèè òàêèõ, êàê ILUT
[3], ILUC [4], RIF Ns� [5], AINV [6], ïîñòðîåíèå ïðåäóñëîâëèâàòåëåé îñíî-
âàíî íà ðàçëîæåíèè âèäà
~ ~ ~
A L D U� , ñîäåðæàùåì äèàãîíàëüíóþ ìàòðèöó
D. Â ïðîöåññå ôàêòîðèçàöèè ïðåíåáðåãàþò íåíóëåâûìè ýëåìåíòàìè l jk è
ukj ìàòðèö L è U, çíà÷åíèÿ êîòîðûõ óäîâëåòâîðÿþò óñëîâèÿì
l Ljk k
T
e
� �1 �, u Ukj k
� �1
e �, (3)
Ñ. Å. Ñàóõ
6 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 6
ãäå � — àïðèîðè çàäàâàåìûé ïðèåìëåìûé óðîâåíü ïîòåðü; e k — âåêòîð ñ
åäèíè÷íûì k-ì ýëåìåíòîì. Âûïîëíÿåìàÿ ïðè óìåíüøàþùèõñÿ çíà÷åíèÿõ
� ILU(�)-ôàêòîðèçàöèÿ ìàòðèöû
~ ~ ~
A L D U�
� ïîçâîëÿåò óìåíüøèòü îøèá-
êó � äî ïðèåìëåìîãî óðîâíÿ, à â ïðåäåëüíîì ñëó÷àå � �0 ïîëó÷èòü � �0,
ò.å. âûïîëíèòü ôàêòîðèçàöèþ â ïîëíîì îáúåìå. Îäíàêî ïðè òàêîì ñïîñîáå
ðåãóëèðîâàíèÿ îøèáêè � íàáëþäàåòñÿ ñóùåñòâåííîå âîçðàñòàíèå ÷èñëà
íåíóëåâûõ ýëåìåíòîâ â ìàòðèöàõ
~
L è
~
U , à øàáëîí P L U
~ ~
ñòàíîâèòñÿ
îòëè÷íûì îò øàáëîíà P A . Ïîýòîìó ILU(�)-ôàêòîðèçàöèÿ, êàê ïðàâèëî,
äîïîëíÿåòñÿ óñëîâèåì, îãðàíè÷èâàþùèì çàïîëíåííîñòü ìàòðèö
~
L è
~
U
íåíóëåâûìè ýëåìåíòàìè â òàêîì êîëè÷åñòâå nz L U(
~ ~
)
, ÷òî
nz L U
nz A
(
~ ~
)
( )
� �. (4)
Àïðèîðè çàäàâàåìîå çíà÷åíèå ïàðàìåòðà � ôàêòè÷åñêè óñòàíàâëèâàåò
ãðàíèöû çàïîëíåííîñòè ôàêòîðíûõ ìàòðèö íåíóëåâûìè ýëåìåíòàìè, íàè-
áîëüøèìè èç íåóäîâëåòâîðÿþùèõ óñëîâèþ (3). Òàêèì îáðàçîì, âû-
ïîëíÿåìàÿ ILU(�� �)-ôàêòîðèçàöèÿ îáåñïå÷èâàåò âîçìîæíîñòü ïîñòðîåíèÿ
ïðåäóñëîâëèâàòåëÿ
~ ~ ~
A L D U� ìàòðèöû A ñ õîðîøèìè àïïðîêñèìàöèîí-
íûìè ñâîéñòâàìè, ÷òî óñêîðÿåò ñõîäèìîñòü èòåðàöèîííûõ ìåòîäîâ ïðîåê-
öèé ðåøåíèé íà ïîäïðîñòðàíñòâà Êðûëîâà [3—5].
Îñíîâíàÿ òðóäíîñòü ðåàëèçàöèè ìåòîäîâ ILU(�� �)-ôàêòîðèçàöèè çà-
êëþ÷àåòñÿ â îöåíêå ìàòðè÷íûõ íîðì e k
T L�1 è U
k
�1
e , âõîäÿùèõ â óñëîâèÿ
(3). Èç ïîñëåäîâàòåëüíî ôîðìèðóåìûõ ñòîëáöîâ è ñòðîê ìàòðèö
~
L è
~
U
íåïîñðåäñòâåííî ïîëó÷èòü òàêóþ îöåíêó íå ïðåäñòàâëÿåòñÿ âîçìîæíûì. Ïî-
ýòîìó ILU(�� �)-ôàêòîðèçàöèÿ ìàòðèöû
~ ~ ~
A L D U� ñîâìåùàåòñÿ ñ AINV (�� �)-
ôàêòîðèçàöèåé îáðàòíîé ìàòðèöû A ZD W� ��1 1 , âûïîëíÿåìîé â íåïîëíîì
âèäå:
~ ~ ~
A ZD W� ��1 1 , ãäå Z è W — âåðõíå- è íèæíåòðåóãîëüíàÿ ìàòðèöû, à
~
Z
è
~
W — àïïðîêñèìèðóþùèå èõ ìàòðèöû [6].
Àëãîðèòìû ñîâìåñòíîé ILU(�� �)- è AINV(�� �)-ôàêòîðèçàöèè òðåáóþò
äîïîëíèòåëüíûõ ðåñóðñîâ îïåðàòèâíîé ïàìÿòè äëÿ ðàçìåùåíèÿ ìàòðèö
~
Z
è
~
W îäíîâðåìåííî ñ ìàòðèöàìè
~
L è
~
U . Â íàèáîëåå ðàöèîíàëüíûõ àëãîðèò-
ìàõ îñóùåñòâëÿåòñÿ ôîðìèðîâàíèå è ðàçìåùåíèå â ïàìÿòè îäíîé èç ìàòðèö
~
Z è
~
W [4, 6]. Îäíàêî òðåáîâàíèå äîïîëíèòåëüíûõ ðåñóðñîâ îïåðàòèâíîé
ïàìÿòè ÿâëÿåòñÿ ñóùåñòâåííûì íåäîñòàòêîì ïîäîáíûõ àëãîðèòìîâ.
Êðîìå òîãî, àëãîðèòìû íåïîëíîé ôàêòîðèçàöèè íåñèììåòðè÷íûõ
ìàòðèö íå âñåãäà ìîãóò îáåñïå÷èòü ïðèåìëåìóþ àïïðîêñèìàöèþ ôàêòîð-
íûõ ìàòðèö â îãðàíè÷åííîé îïåðàòèâíîé ïàìÿòè áåç ïðåäâàðèòåëüíîãî
óïîðÿäî÷åíèÿ ñòðîê è ñòîëáöîâ èñõîäíîé ìàòðèöû A. Ïîñêîëüêó òàêîå
Íåïîëíàÿ ñòîëáöîâî-ñòðî÷íàÿ ôàêòîðèçàöèÿ ìàòðèö
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 6 7
óïîðÿäî÷åíèå íå ó÷èòûâàåò óñëîâèé âû÷èñëèòåëüíîé óñòîé÷èâîñòè ïðî-
öåññà ôàêòîðèçàöèè, íåïîëíàÿ ôàêòîðèçàöèÿ óïîðÿäî÷åííûõ ìàòðèö îñó-
ùåñòâëÿåòñÿ â óñëîâèÿõ êîíòðîëÿ çà áëèçîñòüþ âåäóùèõ ýëåìåíòîâ ê
ìàøèííîìó íóëþ. Âåäóùèå ýëåìåíòû, çíà÷åíèÿ êîòîðûõ íå ïðåâûøàþò
ìàøèííûé íóëü, èñêóññòâåííî êîððåêòèðóþòñÿ, äëÿ òîãî ÷òîáû îáåñïå-
÷èòü óñòîé÷èâîñòü âû÷èñëèòåëüíîãî ïðîöåññà â óùåðá åãî òî÷íîñòè.
Èñêóññòâåííàÿ êîððåêöèÿ âåäóùèõ ýëåìåíòîâ âíîñèò èñêàæåíèÿ â
ôàêòîðíûå ìàòðèöû, îñîáåííî ñóùåñòâåííûå äëÿ ïëîõî îáóñëîâëåíûõ
ìàòðèö. Ïîëó÷àåìûå â ðåçóëüòàòå ïðåäóñëîâëèâàòåëè ÷àñòî îêàçûâàþòñÿ
íåïðèãîäíûìè äëÿ èòåðàöèîííîãî ðåøåíèÿ ëèíåéíûõ ñèñòåì àëãåáðàè-
÷åñêèõ óðàâíåíèé ñ îñîáåííîñòÿìè.
Òàêèì îáðàçîì, ñîâðåìåííûå ìåòîäû íåïîëíîé ôàêòîðèçàöèè ìàòðèö
èìåþò äâà ñóùåñòâåííûõ íåäîñòàòêà: îòñóòñòâèå ïðîöåäóðû âûáîðà âåäóùèõ
ýëåìåíòîâ äëÿ îáåñïå÷åíèÿ âû÷èñëèòåëüíîé óñòîé÷èâîñòè àëãîðèòìà è çíà-
÷èòåëüíî çàâûøåííûå òðåáîâàíèÿ ê èñïîëüçîâàíèþ ðåñóðñîâ îïåðàòèâíîé
ïàìÿòè. Òàêèõ íåäîñòàòîêîâ ëèøåí ïðåäëàãàåìûé ìåòîä ICR-ôàêòîðèçàöèè.
Óñòîé÷èâîñòü ìåòîäà CR-ôàêòîðèçàöèè ìàòðèö. Àíàëèç ñîîòíî-
øåíèé âèäà (1) ñâèäåòåëüñòâóåò îá èòåðàöèîííîì õàðàêòåðå ôîðìóë
CR-ôàêòîðèçàöèè ìàòðèö ñ ÷èñëîì èòåðàöèé n. Äëÿ ìàòðèö áîëüøîé ðàç-
ìåðíîñòè òàêàÿ öåïü âû÷èñëåíèé ìîæåò ïðèâîäèòü ê ñóùåñòâåííîìó íà-
êîïëåíèþ îøèáîê. ×òîáû îáåñïå÷èòü óñòîé÷èâîñòü âû÷èñëèòåëüíîãî
ïðîöåññà, ñëåäóåò íà êàæäîì øàãå ôàêòîðèçàöèè âûáèðàòü âåäóùèé ýëå-
ìåíò, ïîçâîëÿþùèé ìèíèìèçèðîâàòü âëèÿíèå ïðîèçâåäåíèÿ C Rj ik k
íà
ñóáìàòðèöó A i jk k( , )� �� �1 1
, èç êîòîðîé îáðàçóåòñÿ ñóáìàòðèöà A i jk k( , )� � . Äëÿ
ýòîãî ïîèñê âåäóùåãî ýëåìåíòà a i ji j k kk k( , ) ( , )� �� �1 1
â ñóáìàòðèöå A i jk k( , )� �� �1 1
íåîáõîäèìî îñóùåñòâëÿòü â ñîîòâåòñòâèè ñ òðåáîâàíèåì ïîëó÷åíèÿ òàêèõ
ìíîæèòåëåé C jk
è R ik
, êîòîðûå èìåþò ìèíèìàëüíî âîçìîæíóþ íîðìó:
A Ai j i j j i j i
i jk k k k k k k k
k k
( , ) ( , )
( , )
min� � � �� � � �
� �1 1
C R C R . (5)
Çäåñü è íèæå ñèìâîëîì îáîçíà÷åíà îêòàýäðàëüíàÿ íîðìà. Âûáîð èìåí-
íî òàêîé íîðìû îáúÿñíÿåòñÿ ïðîñòîòîé àëãîðèòìà åå âû÷èñëåíèÿ, à ãëàâ-
íîå, óñòîé÷èâîñòüþ ïîëó÷àåìûõ ðåçóëüòàòîâ ê âû÷èñëèòåëüíûì îøèá-
êàì. Ïîñêîëüêó
C j ij
i
i j k
i
i j
k k
k k
k k
c
a i j
r
� �
� �� �( , )
,
( , )
1 1
,
(6)
R i i j
j
i j k
j
i j
k k
k k
k k
r
a i j
c
� �
� �� �( , )
,
( , )
1 1
, (7)
Ñ. Å. Ñàóõ
8 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 6
a i j c ri j k k i j i jk k k k k k( , ) ( , )� �� �
�
1 1
, à òàêæå ñòîëáåö jk è ñòðîêà ik ñóáìàòðèöû
A i jk k( , )� � ÿâëÿþòñÿ íóëåâûìè, èç (5), ñ ó÷åòîì (1), íàõîäèì óòî÷íåííîå
âûðàæåíèå:
[ ( ,*) ( , ) ]( , ) ( , )A i a i ji j k i j k kk k k k� � � �� � � �
� �
1 1 1 1
�
�� � � �
�
� � � �
[ (*, ) ( , ) ]( , ) ( , )
(
A j a i j
a
i j k i j k k
i
k k k k
k
1 1 1 1
� ��
�
1 1, )
( , )( , )
min
j k k
i j
k
k ki j
,
(8)
ãäå
A j a i ji j k
i
i j kk k k k( , ) ( , )(*, ) ( , )� � � �� � � �
� 1 1 1 1
,
A i a i ji j k
j
i j kk k k k( , ) ( , )( ,*) ( , )� � � �� � � �
� 1 1 1 1
.
Êðèòåðèé (8) ëåãêî ðåàëèçóåì, ïîñêîëüêó íàõîæäåíèå âõîäÿùèõ â íåãî
íîðì îñóùåñòâëÿåòñÿ ðåêóððåíòíî è íå òðåáóåò çíà÷èòåëüíûõ âû÷èñëèòåëü-
íûõ çàòðàò. Êðîìå òîãî, äëÿ ïîèñêà âåäóùåãî ýëåìåíòà a i ji j k kk k( , ) ( , )� �� �1 1
íåò
íåîáõîäèìîñòè âûïîëíÿòü îöåíêè ôóíêöèîíàëà â âûðàæåíèè (8) äëÿ âñåõ
ýëåìåíòîâ ñóáìàòðèöû A i jk k( , )� �� �1 1
. Ïîèñê âåäóùåãî ýëåìåíòà äîñòàòî÷íî
îcóùåñòâèòü â n nk �� íåíóëåâûõ ñòðîêàõ ñóáìàòðèöû A i jk k( , )� �� �1 1
, ñîäåð-
æàùèõ íàèìåíüøåå ÷èñëî íåíóëåâûõ ýëåìåíòîâ. Òàêîé ñïîñîá ïîèñêà
âåäóùåãî ýëåìåíòà íå òîëüêî îáåñïå÷èâàåò óñòîé÷èâîñòü âû÷èñëåíèé, íî
è óìåíüøàåò ðàçëè÷èå ìåæäó øàáëîíàìè ñóáìàòðèö A i jk k( , )� �� �1 1
è A i jk k( , )� � .
Àíàëèçèðóÿ âûðàæåíèÿ (5) è (8), çàìå÷àåì, ÷òî ïðåäåëüíîå (íóëåâîå)
çíà÷åíèå ôóíêöèîíàëà â (8) äîñòèãàåòñÿ ïðè óñëîâèè, ÷òî âåäóùèé ýëå-
ìåíò âûáèðàåòñÿ íà ïåðåñå÷åíèè ñòðîêè è ñòîëáöà, êîãäà â îäíîì èç íèõ
èìååòñÿ òîëüêî îäèí ýëåìåíò, îòëè÷íûé îò íóëÿ.  ýòîì ñëó÷àå ïðè ïåðå-
õîäå îò ñóáìàòðèöû A i jk k( , )� �� �1 1
ê ñóáìàòðèöå A i jk k( , )� � îøèáîê íå âîçíè-
êàåò.  îñòàëüíûõ ñëó÷àÿõ âîçìîæíû îøèáêè â êîìïüþòåðíûõ âû÷èñëå-
íèÿõ, îäíàêî èõ ÷èñëî îãðàíè÷åíî òåì áîëüøå, ÷åì ìåíüøå çíà÷åíèå
ôóíêöèîíàëà â âûðàæåíèè (5).
Ìåòîä ICR-ôàêòîðèçàöèè ìàòðèö. Îáðàùàÿñü ê ðåêóððåíòíûì ñîîò-
íîøåíèÿì âèäà (1), îïðåäåëèì óñëîâèÿ, ïðè êîòîðûõ ìîæíî ïðåíåáðå÷ü
âëèÿíèåì ñòðîê è ñòîëáöîâ ôîðìèðóåìûõ ôàêòîðíûõ ìàòðèö íà ñóáìàò-
ðèöû. Î÷åâèäíî, â ñëó÷àå íåñîïîñòàâèìîñòè ñòðî÷íûõ è ñòîëáöîâûõ
îêòàýäðàëüíûõ íîðì ñîîòâåòñòâóþùèõ âåêòîðîâ, à èìåííî
c A iij i i jk k k k
R �� � �� �( , ) ( ,*)
1 1
(9)
è
r A ji j j i jk k k k
C �� � �� �( , ) (*, )
1 1
, (10)
Íåïîëíàÿ ñòîëáöîâî-ñòðî÷íàÿ ôàêòîðèçàöèÿ ìàòðèö
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 6 9
ýëåìåíòû cijk
è ri jk
îêàçûâàþòñÿ íåñóùåñòâåííûìè è ìîæíî ïîëàãàòü, ÷òî
îíè ðàâíû íóëþ.
Äëÿ îöåíêè çíà÷èìîñòè ýëåìåíòîâ cijk
è ri jk
íåò íåîáõîäèìîñòè â
ïðåäâàðèòåëüíîì âû÷èñëåíèè ñòîëáöà C jk
è ñòðîêè R ik
, òàê êàê âûðàæå-
íèÿ (9) è (10), ñ ó÷åòîì (6) è (7), ìîæíî ïðåäñòàâèòü â òîæäåñòâåííîì âèäå:
c
c
A i
A i
ij
i j
i j
i j k
k
k k
k k
k k
��
� �
� �
� �
� �
( , )
( , )
( ,*)
( ,*)
1 1
1 1
�
� �
� �
� �
� �
j
i j
j
i j k
a i j
a i j
k k
k k
( , )
( , )
( , )
( , )
1 1
1 1
, (11)
r
r
A j
A j
a
i j
i j
i j
i j k
i
i
k
k k
k k
k k
k
�� �
� �
� �
�
( , )
( , )
((*, )
(*, )
� �
� �
�
� �
1 1
1 1
, )
( , )
( , )
( , )
j
i
i j k
k
k k
i j
a i j
. (12)
Ïîëó÷åííûå ñîîòíîøåíèÿ ïîçâîëÿþò îöåíèâàòü çíà÷èìîñòü ýëåìåí-
òîâ ñòîëáöà C jk
è ñòðîêè R ik
, îñíîâûâàÿñü òîëüêî íà ñîîòíîøåíèÿõ íîðì
ìåæäó ñîîòâåòñòâóþùèìè ñòðîêàìè è ñòîëáöàìè ñóáìàòðèöû A i jk k( , )� �� �1 1
.
Ïàðàìåòðèçàöèÿ âûðàæåíèé (11) è (12) ïîçâîëÿåò ïðåäñòàâèòü èõ â âèäå
c
c
a i j
a i
ij
i j
j
i j
j
i j
k
k k
k k
k k
�
� �
� �
� �
� �
�
( , )
( , )
( , )
(
1 1
1 1 k j, )
(13)
è
r
r
a i j
a i
i j
i j
i
i j
i
i j
k
k k
k k
k k
�
� �
� �
� �
� �
�
( , )
( , )
( , )
(
1 1
1 1
, )jk
, (14)
óäîáíîì äëÿ ïðàêòè÷åñêîãî èñïîëüçîâàíèÿ. Ïðè ýòîì àïðèîðè çàäàâàåìîå
çíà÷åíèå ïàðàìåòðà � óñòàíàâëèâàåò ãðàíèöó ðàçäåëà ýëåìåíòîâ cijk
è ri jk
íà çíà÷èìûå è íåçíà÷èìûå.  ïðîöåññå ôàêòîðèçàöèè çíà÷èìûå ýëåìåíòû
ñîõðàíÿþòñÿ â ñòîëáöàõ
~
C jk
è ñòðîêàõ
~
R ik
.
Ó÷èòûâàÿ òîæäåñòâåííîñòü âûðàæåíèé (13) è (14) âûðàæåíèÿì (9) è
(10), îòáðàñûâàíèå ìàëîçíà÷èìûõ ýëåìåíòîâ cijk
è ri jk
â ôîðìóëàõ (1)
ìîæíî èíòåðïðåòèðîâàòü êàê îøèáêè ìàøèííûõ âû÷èñëåíèé, à ïàðàìåòð
� ðàññìàòðèâàòü â êà÷åñòâå îáîáùåííîé õàðàêòåðèñòèêè òàêèõ îøèáîê.
Ìåòîä ôàêòîðèçàöèè ìàòðèö, îñíîâàííûé íà ôîðìóëàõ (1) ïðè âûáîðå
âåäóùèõ ýëåìåíòîâ â ñîîòâåòñòâèè ñ êðèòåðèåì (8) è ïðåíåáðåæåíèè
ýëåìåíòàìè ôàêòîðíûõ ìàòðèö, óäîâëåòâîðÿþùèõ óñëîâèÿì (13), (14),
íàçûâàåòñÿ ìåòîäîì íåïîëíîé ñòîëáöîâî-ñòðî÷íîé ôàêòîðèçàöèè ìàòðèö,
èëè ìåòîäîì ICR-ôàêòîðèçàöèè.
Ñ. Å. Ñàóõ
10 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 6
 ñëó÷àå ICR-ôàêòîðèçàöèè ïëîõî îáóñëîâëåííûõ ìàòðèö ÷óâñòâè-
òåëüíîñòü ðåøåíèé ê îøèáêàì ñóùåñòâåííî âîçðàñòàåò, è ïîýòîìó ïàðàìåòð �
â (13) è (14) ñëåäóåò âûáèðàòü ìàëûì íàñòîëüêî, íàñêîëüêî íåîáõîäèìî
óìåíüøèòü âëèÿíèå ïîäîáíûõ îøèáîê. Î÷åâèäíî, äëÿ 32-õðàçðÿäíûõ âû÷èñ-
ëèòåëüíûõ ñèñòåì âûáîð çíà÷åíèÿ ïàðàìåòðà � ìåíüøå âåëè÷èíû 10–16 ñìûñ-
ëà íå èìååò, ïîñêîëüêó òàêîé âûáîð ýêâèâàëåíòåí óñòàíîâëåíèþ çíà÷åíèÿ
� �0 è, ñëåäîâàòåëüíî, âûïîëíåíèþ ïîëíîé CR-ôàêòîðèçàöèè. Â áîëüøèíñò-
âå ñëó÷àåâ çíà÷åíèå ïàðàìåòðà � óñòàíàâëèâàåòñÿ â ïðåäåëàõ îò 10–1 äî 10– 4,
÷òî äîñòàòî÷íî äëÿ ïîñòðîåíèÿ ýôôåêòèâíûõ ïðåäóñëîâëèâàòåëåé.
Ðåçóëüòàòû ýêñïåðèìåíòàëüíûõ èññëåäîâàíèé. Òåñòèðîâàíèå ïðåä-
ëîæåííîãî ìåòîäà âûïîëíåíî íà ïðèìåðàõ íåñèììåòðè÷íûõ ìàòðèö [5],
îñíîâíûå õàðàêòåðèñòèêè êîòîðûõ ïðèâåäåíû â òàáë. 1, ãäå óêàçàíû òàêæå
íàèìåíîâàíèÿ òåñòîâûõ ìàòðèö, ïî êîòîðûì èõ ìîæíî íàéòè â èíòåðíåòå,
Íåïîëíàÿ ñòîëáöîâî-ñòðî÷íàÿ ôàêòîðèçàöèÿ ìàòðèö
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 6 11
Íàçâàíèå ìàòðèöû
â èíòåðíåòå
n nz
raefsky5 6 316 167 178
raefsky6 3 402 130 371
ASIC_100ks 99 190 578 890
FEM_3D_thermal1 17 880 430 740
FEM_3D_thermal2 147 900 3 489 300
sme3Da 12 504 874 887
sme3Db 29 067 2 081 063
dc3 116 835 766 396
trans4 116 835 749 800
trans5 116 835 766 396
raefsky1 3 242 293 409
raefsky2 3 242 293 551
raefsky3 21 200 1 488 768
hcircuit 105 676 513 072
ASIC_680ks 682 712 1 693 767
ASIC_320k 321 821 1 931 828
ASIC_320ks 321 671 1 316 085
ASIC_100k 99 340 940 621
epb3 84 617 463 625
poisson3Da 13 514 352 762
sme3Dc 42 930 3 148 656
stomach 213 360 3 021 648
Òàáëèöà 1
Ñ. Å. Ñàóõ
12 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 6
Òèï êîìïüþòåðà IBM System x3850 Desktop Computer
Ïðîöåññîð:
ðàçðÿäíîñòü 64-bit 32-bit
SMP, øò. 4 1
òèï Intel Xeon MP Intel Pentium 4
÷àñòîòà 3.66 GHz 3.0 GHz
÷àñòîòà øèíû 667 MHz 800 MHz
îáúåì êýø-ïàìÿòè L2 1 MB 1 MB
Ïàìÿòü: DDR2 dual DDR dual
îáúåì 16 GB 1 GB
ñêîðîñòü äîñòóïà 400 MHz 400 MHz
Îïåðàöèîííàÿ ñèñòåìà Íåèçâåñòíà Microsoft Windows XP
Êîìïèëÿòîð:
ÿçûê
òèï
Fortran-90
Intel Compiler ifort
C++
Microsoft Visual Studio 2008
ïàðàìåòð îïòèìèçàöèè O4 Full
Òàáëèöà 2
Íàçâàíèå ìàòðèöû â èíòåðíåòå ICR left-RIF right-RIF AINV ILUC
Raefsky5
Raefsky6
ASIC_100ks
FEM_3D_thermal1
FEM_3D_thermal2
Sme3Da
Sme3Db
dc3
trans4
trans5
raefsky1
raefsky2
raefsky3
hcircuit
ASIC_680ks
ASIC_320k
ASIC_320ks
ASIC_100k
epb3
poisson3Da
sme3Dc
stomach
5
4
12
10
9
1610
2193
15
8
10
30
49
87
4
36
19
2
21
133
22
2002
6
5
8
10
11
10
—
—
73
25
56
33
88
—
29
7
13
4
13
136
26
—
6
5
5
10
9
8
2434
—
73
23
37
33
67
149
59
7
16
4
17
104
26
—
6
9
9
30
27
23
—
—
60
11
17
708
842
—
—
34
—
16
221
693
141
—
74
5
4
8
5
5
1903
—
50
21
45
118
135
74
11
33
8
5
8
92
16
—
5
Òàáëèöà 3
ðàçìåðíîñòè ìàòðèö n è ÷èñëî ñîäåðæàùèõñÿ â íèõ íåíóëåâûõ ýëåìåíòîâ
nz. Âñå ðàñ÷åòû âûïîëíåíû íà âû÷èñëèòåëüíîì óñòðîéñòâå Desktop Com-
puter, ïàðàìåòðû êîòîðîãî, à òàêæå õàðàêòåðèñòèêè èñïîëüçîâàíîãî ïðî-
ãðàììíîãî îáåñïå÷åíèÿ ïðåäñòàâëåíû â òàáë. 2. Äëÿ ñðàâíåíèÿ â òàáë. 2
ïðèâåäåíû òàêæå õàðàêòåðèñòèêè âû÷èñëèòåëüíîãî óñòðîéñòâà IBM Sys-
tem x3850 è ïðîãðàììíîãî îáåñïå÷åíèÿ, èñïîëüçîâàííûõ â ðàáîòå [5] äëÿ
ôàêòîðèçàöèè òåõ æå òåñòîâûõ ìàòðèö.
Ñîïîñòàâëåíèå ïîëó÷åííûõ ðåçóëüòàòîâ ñ ðåçóëüòàòàìè, ïðåäñòàâëåí-
íûìè â ðàáîòå [5], âûïîëíåíî â óñëîâèÿõ îãðàíè÷åíèÿ òðåáîâàíèé ê èñ-
ïîëüçóåìûì ðåñóðñàì ïàìÿòè äëÿ ðàçìåùåíèÿ ôàêòîðíûõ ìàòðèö
~
C è
~
R
òåìè îáúåìàìè ïàìÿòè, êîòîðûå èñïîëüçîâàëèñü â [5] äëÿ ðàçìåùåíèÿ
ìàòðèö
~
L è
~
U .
 òàáë. 3 ïðèâåäåíî ÷èñëî èòåðàöèé ìåòîäà GMRES(30) ñ ðàçëè÷íûìè
ïðåäîáóñëîâëèâàòåëÿìè. Êàê âèäíî èç òàáë. 3, ðåçóëüòàòû ýêñïåðèìåíòîâ ñâè-
äåòåëüñòâóþò î ïîäîáíîñòè àïïðîêñèìàöèîííûõ ñâîéñòâ ïðåäîáóñëîâëèâà-
òåëåé, ïîëó÷åííûõ ìåòîäàìè ICR-, left-RIF�Ns-, right-RIF�Ns-, AINV-, ILUC-
ôàêòîðèçàöèè, íåñìîòðÿ íà òî ÷òî ICR-ôàêòîðèçàöèÿ ìàòðèö îñóùåñòâëÿëàñü
áåç âûïîëíåíèÿ óñëîâèÿ (4) äëÿ îòñå÷åíèÿ ýëåìåíòîâ ìàòðèö
~
C è
~
R.
 áîëüøèíñòâå òåñòîâ çàòðàòû âðåìåíè íà ôàêòîðèçàöèþ îêàçàëèñü
ñîïîñòàâèìûìè. Ïðåèìóùåñòâà ìåòîäà ICR-ôàêòîðèçàöèè âåñüìà ñóùåñò-
âåííû äëÿ ìàòðèö dc3, trans4, trans5, ê êîòîðûì èçâåñòíûå ìåòîäû ôàêòî-
ðèçàöèè ïðèìåíÿëèñü áåç èñïîëüçîâàíèÿ ïðîöåäóð ïðåäâàðèòåëüíîãî óïî-
ðÿäî÷åíèÿ ìàòðè÷íûõ ñòðîê è ñòîëáöîâ. Ïðåèìóùåñòâî çàêëþ÷àåòñÿ â
ìíîãîêðàòíîì (â 2—3 ðàçà) óñêîðåíèè ñõîäèìîñòè èòåðàöèîííûõ ïðîöå-
äóð â ñëó÷àå èñïîëüçîâàíèÿ ICR-ïðåäîáóñëîâëèâàòåëÿ.
Âûâîäû. Ïðåäëîæåííûé ìåòîä íåïîëíîé ñòîëáöîâî-ñòðî÷íîé ôàêòî-
ðèçàöèè íåñèììåòðè÷íûõ ìàòðèö îòëè÷àåòñÿ îò èçâåñòíûõ ìåòîäîâ ILU-,
AINV- è RIF�Ns-ôàêòîðèçàöèè îòñóòñòâèåì äîïîëíèòåëüíûõ òðåáîâàíèé ê
èñïîëüçóåìûì ðåñóðñàì ïàìÿòè, êðîìå íåîáõîäèìûõ äëÿ ðàçìåùåíèÿ
ôàêòîðíûõ ìàòðèö. Âû÷èñëèòåëüíàÿ óñòîé÷èâîñòü ìåòîäà îáåñïå÷èâàåòñÿ
ïðèìåíåíèåì îðèãèíàëüíîé ïðîöåäóðû ïîèñêà âåäóùèõ ýëåìåíòîâ â ñóá-
ìàòðèöàõ. Ïîèñê âûïîëíÿåòñÿ â îãðàíè÷åííîì ìíîæåñòâå ñòðîê ñ íàè-
ìåíüøèì ÷èñëîì íåíóëåâûõ ýëåìåíòîâ.
Íîâûé ìåòîä ñîäåðæèò îðèãèíàëüíóþ ïðîöåäóðó âûáîðà âåäóùèõ
ýëåìåíòîâ, ÷òî îáåñïå÷èâàåò óñòîé÷èâîñòü âû÷èñëåíèé ê îøèáêàì îêðóã-
ëåíèÿ è îøèáêàì îòñå÷åíèÿ ìàëîçíà÷èìûõ ýëåìåíòîâ.
Ïðåèìóùåñòâà ïðåäëîæåíîãî ìåòîäà IRC-ôàêòîðèçàöèè íàä ìåòîäîì
ILU-ôàêòîðèçàöèè è åãî ìîäèôèêàöèÿìè çàêëþ÷àåòñÿ â äîñòèæåíèè âûñî-
êîé àïïðîêñèìàöèîííîé òî÷íîñòè ôîðìèðóåìûõ ôàêòîðíûõ ìàòðèö ïðè
ýêîíîìè÷íîì èñïîëüçîâàíèè ðåñóðñîâ ïàìÿòè, ÷òî ïîäòâåðæäàåòñÿ ýêñïå-
Íåïîëíàÿ ñòîëáöîâî-ñòðî÷íàÿ ôàêòîðèçàöèÿ ìàòðèö
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 6 13
ðèìåíòàëüíî íà ìíîæåñòâå òåñòîâûõ ïðèìåðîâ ïðè èñïîëüçîâàíèè ìàòðèö
~
C è
~
R â êà÷åñòâå ïðåäîáóñëîâëèâàòåëåé â èòåðàöèîííûõ ìåòîäàõ Êðûëîâà
òèïà GMRES(m) è BiCGStab.
A method of the column-line (ICR) factorization of asymmetrical matrices is proposed for form-
ing predeterminers. The method does not require permutation of lines and columns in sub-
matrices. The obtained factor matrices are not triangular. The original procedure of the search for
the leading element in the submatrix by the criterion of minimum of divergence by the Frobenius
norm between the transformable and transformed submatrices provides for the stability of calcu-
lations for badly determined matrices. An original estimation of the value of the factor matrices
elements is used in the method of ICR-factorization. The examples of solution for the test equa-
tion systems with the use of iterational methods of solution projections to Krylov’s subspaces are
presented which confirm the advantages of the proposed method.
1. Ñàóõ Ñ. Å. Ìåòîä CR-ôàêòîðèçàöèè ìàòðèö áîëüøîé ðàçìåðíîñòè // Ýëåêòðîí. ìîäå-
ëèðîâàíèå. — 2007. — 29, ¹ 6. — C. 3—20.
2. Îðòåãà Äæ. Ââåäåíèå â ïàðàëëåëüíûå è âåêòîðíûå ìåòîäû ðåøåíèÿ ëèíåéíûõ ñèñ-
òåì. — M. : Ìèð, 1991. — 386 ñ.
3. Saad Y. Iterative Methods for Sparse Linear Systems. — Minneapolis: University of Minne-
sota MN, 2000. — 448 p.
4. Li N., Saad Y., Chow E. Crout Versions of ILU for General Sparse Matrices // SIAM Journal
on Scientific Computing. — 2003. — Vol. 25. —- P. 716—728.
5. Rafiei A., Bollhöfer M. Robust Incomplete Factorization for Nonsymmetric Matrices. —
http://www.math.tu-berlin.de/numerik/mt/NumMat/Publikationen/search.html
6. Benzi M., Tuma M. A Sparse Approximate Inverse Preconditioner for Nonsymmetric Linear
Systems // SIAM Journal on Scientific Computing. — 1998. — Vol. 19. — P. 968—994.
7. Ýñòåðáþ Î., Çëàòåâ Ç. Ïðÿìûå ìåòîäû äëÿ ðàçðåæåííûõ ìàòðèö. — M. : Ìèð, 1987. —
120 c.
Ïîñòóïèëà 10.09.10
ÑÀÓÕ Ñåðãåé Åâãåíüåâè÷, ä-ð òåõí. íàóê, ãë. íàó÷. ñîòð. Èí-òà ïðîáëåì ìîäåëèðîâàíèÿ â
ýíåðãåòèêå èì. Ã. Å. Ïóõîâà ÍÀÍ Óêðàèíû.  1978 ã. îêîí÷èë Êèåâñêèé èí-ò èíæåíåðîâ ãðàæ-
äàíñêîé àâèàöèè. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ÷èñëåííûå îïåðàòîðíûå ìåòîäû ðåøåíèÿ
äèôôåðåíöèàëüíûõ óðàâíåíèé, äåêîìïîçèöèîííûå è èòåðàöèîííûå ìåòîäû ðåøåíèÿ ëèíåéíûõ
ñèñòåì áîëüøîé ðàçìåðíîñòè, ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå òåõíîëîãè÷åñêèõ ïðîöåññîâ â
ýíåðãåòèêå è ãàçîòðàíñïîðòíûõ ñèñòåìàõ, ýêîíîìèêî-ìàòåìàòè÷åñêèå ìåòîäû ìîäåëèðî-
âàíèÿ ôèíàíñîâûõ è ìàêðîýêîíîìè÷åñêèõ ïðîöåññîâ.
Ñ. Å. Ñàóõ
14 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 6
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJDFFile false
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/Description <<
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|
| id | nasplib_isofts_kiev_ua-123456789-61684 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-12-07T18:40:38Z |
| publishDate | 2010 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Саух, С.Е. 2014-05-10T15:42:15Z 2014-05-10T15:42:15Z 2010 Неполная столбцово-строчная факторизация матриц для итерационного решения больших систем уравнений / С.Е. Саух // Электронное моделирование. — 2010. — Т. 32, № 6. — С. 3-14. — Бібліогр.: 7назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/61684 519.612 Для формирования предобусловливателей предложен метод неполной столбцово-строчной (ICR) факторизации несимметричных матриц. Метод не требует перестановок строк и столбцов в субматрицах. Получаемые факторные матрицы не являются треугольными. Оригинальная процедура поиска ведущего элемента в субматрице по критерию минимума расхождения по норме Фробениуса между преобразуемой и преобразованной субматрицами обеспечивает устойчивость вычислений для плохо обусловленных матриц. В методе ICR-факторизации применена оригинальная оценка значимости элементов факторных матриц, основанная на сопоставлении норм строк и столбцов преобразуемых и вычитаемых субматриц. Приведены примеры решения тестовых систем уравнений с использованием итерационных методов проекций решений на подпространства Крылова, подтверждающие преимущества предложеного метода. Для формування передобумовлювачів запропоновано метод неповної стовпцево-рядкової (ICR) факторизації несиметричних матриць. Метод не потребує перестановок рядків і стовпців у субматрицях. Одержувані факторні матриці не є трикутними. Оригінальна процедура пошуку провідних елементів в субматрицях за критерієм мінімальної розбіжності по нормі Фробеніуса між перетворюваною і перетвореною субматрицями забезпечує стійкість обчислень для погано обумовлених матриць. У методі ICR-факторизації застосовано оригінальну оцінку значимості елементів факторних матриць, базовану на зіставленні норм рядків і стовпців перетворюваних субматриць та субматриць, що віднімаються. Наведено приклади розв’язку тестових систем рівнянь з використанням ітераційних методів проекцій розв’язків на підпростори Крилова, які підтверджують переваги запропонованого методу. A method of the column-line (ICR) factorization of asymmetrical matrices is proposed for forming predeterminers. The method does not require permutation of lines and columns in submatrices. The obtained factor matrices are not triangular. The original procedure of the search for the leading element in the submatrix by the criterion of minimum of divergence by the Frobenius norm between the transformable and transformed submatrices provides for the stability of calculations for badly determined matrices. An original estimation of the value of the factor matrices elements is used in the method of ICR-factorization. The examples of solution for the test equation systems with the use of iterational methods of solution projections to Krylov’s subspaces are presented which confirm the advantages of the proposed method. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математические методы и модели Неполная столбцово-строчная факторизация матриц для итерационного решения больших систем уравнений Article published earlier |
| spellingShingle | Неполная столбцово-строчная факторизация матриц для итерационного решения больших систем уравнений Саух, С.Е. Математические методы и модели |
| title | Неполная столбцово-строчная факторизация матриц для итерационного решения больших систем уравнений |
| title_full | Неполная столбцово-строчная факторизация матриц для итерационного решения больших систем уравнений |
| title_fullStr | Неполная столбцово-строчная факторизация матриц для итерационного решения больших систем уравнений |
| title_full_unstemmed | Неполная столбцово-строчная факторизация матриц для итерационного решения больших систем уравнений |
| title_short | Неполная столбцово-строчная факторизация матриц для итерационного решения больших систем уравнений |
| title_sort | неполная столбцово-строчная факторизация матриц для итерационного решения больших систем уравнений |
| topic | Математические методы и модели |
| topic_facet | Математические методы и модели |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/61684 |
| work_keys_str_mv | AT sauhse nepolnaâstolbcovostročnaâfaktorizaciâmatricdlâiteracionnogorešeniâbolʹšihsistemuravnenii |