В работе рассматривается параллельный алгоритм вычислреанзиряеженного QR зр-а ложения специальным образом упорядоченной прямоугольной матрицы на основе разреженных блочных преобразования Хаусхолдера. Для построения необходимого упорядочивания можно использоватсьтолбцевое упорядочивание типа вложенных сечений, потсроенное по структуре матрицыTA,A где A- исходная прямоугольная матрица. Для сеточных задач упорядочивание может быть построено на з-основе и вестного объемного биения расчетной сетки. В качестве базового алгоритрм-а для о ганизации параллельных вычислений спиользуется QR разложение для наборов строк матрицы с дополнением в виде нулевого начального блока. Алгориот-м предп лагается использовать в качестве вычислительного ядра разрабатываемых автором параллельных итерационных алгоритмов решения СЛАУ и задачньншаихме квдаратов на основе композиции подпространств, порождаемых разреженными базисами.
алгоритмам решения СЛАУ и задач наименьших квадратов на основе комппоодзпирцои-и странств, порождаемых разреженными базисами.
Работа построена следующим образом. В Раздеолпеисы2вается блочное преобразование Хаусхолдера [7] и его применение для профильнроазйреженной QR факторизации пряомугольной матриц ы, аналогичной использмуеым в работах4],[5]. В Разделе 3 описывается о-алг ритм вычислениярасширенного профильногоразреженного QR разложения с борлаезереженным во многих практических случQаяхфактором для матриц ы, расширеннойквадратным нулевым начальнымблоком. Проводится сравнение профильного и расширеннпоргофильного разреженного QR разложения для некотормыатхриц. В Разделе 4 описывается построение QR разложения матрицы в случае строчного биения матВрицРыа.зделе5 вводится понятие вхерней квази- треугольной матрицы с разреженностью типа вложенных сечений и привао-дится п раллельный алгоритм вычисления разреженного QR разложения для такой матрицы. В Разделе 6 описывается способ вычисленисятолбцевого истрочного упорядочиваний и биений, котеоры приводят матрицу, заданную на объемной сетке с известным объемным геометричесик-их биен ем, к виду верхней к-втарзиеугольной матрицы с разреженностью типа вложенных сечений. 2. Блочное преобразование Хаусхолдера и профильное разреженное QR разложение 2.1 Блочное преобразование Хаусхолдера Классическое преобразование Хаусхолдер—а это унитарная матрица ви[д1а]: , (2.1) где - некоторый вектор, - некоторое вещественное число. При этом строится па-реобр зование Хаусхолдера как правило из условия, чтобы для некоторого векторва векторе все компоненты кромзеаданного набора начальных компонебнытли нулевыми.
Рассмотрим прямоугольную матрицу . Классический алгоритм[1] вычисления QR разложения этой матрицы на основе преобразований Хаусхол2д.1е)рапр(иводит к соо-тн шениям: , (2.2) где матрица - квадратная верхняя треугольная, а матрицы - ортогональные матрицы преобразования Хаусхолдера, имеющие вид , где - некоторое число, - некоторый вектор, первые компонент которого нулевые. Расширение QR разложения для расширенной на один столбец матрицы , как это хорошзо- и вестно, можно вычислить применением в соответствующем порядке транспонированен-ых пр образований Хаусхолдера к столбцуи построением нового преобразования ХаусхолдДерлая. явного нахождения -го базисного вектора- фQактора QR разложения в неявной фор.м2)е (2 достаточно вычислить результат умжнеония: где - - й единичный орт.
Обозначим . Рассмотрим хорошо известн[о7е] блочное обобщение преоба-р
зований Хаусхолдера2.(
, тогда, как легко проверить, имеет место равенство 2(.4) в том числе и для , при этом и .
Таким образом получаетссяледующая последовательность вычислений блочного преоа-бр зования Хаусхолдера. Сначала вычисляется обычное векторное QR разложение матрди-цы с о но- векторными преобразованиями Хаусхолдера. Из полученных наборов векторов сотс-тавляе ся матрица . Далее вычисляется матрица и по ней по рекуррентным формуыла-м в числяется матрица . Подобная организация вычислений позволэяфефтективно использовтаь векторные вычисления на основеSIMD инструкций [6].
В последующем изложении мбыудем рассматривать вопросы вычисления QR разложения для прямоугольных так называеммыехлко блочно разреженных матриц. Это означает, зч-то ра реженность понимается в смысле блоков малого размера, каждый из которых является плотной в общем случае прямоугольной матрицей. Для простоты последующего изложения мы будем предполагать, что строчные стиолбцевые размеры всех мелких блоков совпадают между собой и равны некоторому малому значени, ю . При этом все представленные в рабоот-е алг ритмы могут быть легко обобщены на случай переменного столбцсетвроогчоногио мелко блочного биения. В противевсо мелкимплотным блокам мы будем говорить также о крупно- блочном или просто блочном биении, строчном и столбцевом. Это всегдаа-будет озн чать, что соответствующие подматрицы составлены из некоторого количества мелко блочных строк и столбцоПв.ри этом под блочным преобразованием Хаусхолдера мы всегда будем иметь в виду преобразование (2.4) для одного мелко блочного столбца. 2.2 Профильное разреженное QR разложение
Блочные преобразования Хаусхолдера (2.4) можно применить для вычисления раоз-реженн го QR разложения разреженной матрицы , составленной из мелко блочныхстолбцов. Для этого можно поступить например следующим образом. Для минимизации заполнения R- фактора QR разложения ывчисляем структуру разреженности матрицы и вычисляем упорядочивание, минимизирующее заполнение матрицыс такой структурой при еетреугольной факторизации. Можно выбрат,ь например, упорядочивание вложенных сечений ND или упорядочивание RCM 2][. Это опрелдяеет упорядочиваниемелко блочныхстолбцов матрицы . Далее упорядочиваниемелко блочныхстрок можно выбрать последовательно нумеруая- сн чала элементы первого столбца, потом второго, и т.д. Переупорядоченная таким образом матрица будет иметь вид типа приведенного на Риссулнеквае. В1 качестве базового столеб-ц вого упорядочивания для этой матрицы было выбрано упорядочиNвDан.ие Рис. 1. Структуры разреженности матрицыи ее -Qи R- факторов для тестовой задачи При построении так называемого профильнроагзореженного QR разложения таким а-обр зом упорядоченноймелко блочнойматрицы будем действовать по аналогии со случаетм- пло ной матрицы. По первомеулко блочному столбцу матрицы строим разрненжое блочное пе-р образование Хаусхолдера с разреженностью сцтоалбтакой, чтобы обнулить мелкие блокти- ма рицы подпервой блочной диагональю. Применяем транспонированное блочное преобар-азов ние Хаусхолдера ко второмумелко блочномустолбцу, для полученного результата строиме- сл дующее разреженное блочное преобразованХиеаусхолдера для обнуления элементов подо- вт рой мелко блочной диагональю, и т.д. На Рис. 1 справа показана мелко блочная разреженность Q- и R- факторов QR разложения для матрицсылева. Для этого теста заметно довольноь- сил ное заполнение в- фQакторе внурти соответствующего профиля матрицы. 3. Расширенное профильное разреженное QR разложение
Профильное разреженное QR разложенмиаетрицы, описанное выш,е не является едитн-с венным вариантом построения QR разложенСиуящ.ествует вариант, для которого болеее- ест ственным образом выделяется его параллельная структура, и который во многих практически важных случаях приводит к меньшему заполнению в факторе Q. Это так назывиа-емое расш ренное профильное QR разложение.
Схематически профильное и расширеннпореофильное QR изображены на Рисунке 2.к-Фа тически расширенноепрофильное QR разложение- это профильное QR разложение, пер-им ненное к матрице, расширенной сверху нулекввыадмратным блоком. При этом структураз- ра реженности Q фактора пополняется возможными дополнительнылеммиенэтами на местбеывшего фактора R, и отсоединенными диагональными элементами, примыкающимниовокму R фактору.
Рис. 2. Профильное (слева) и расширенпнрооефильное (справа) QR разложения Покажем прежде всего, что в случае матрипцоылного столбцевого ранга профильное и расширенное профильное QR разложения математически эквивалентны. Обозначим . Для матрицы полного столбцевого рангаматрица невырождена и являетсоячевидно треугольным фактором матрицы , а значимтатрица является R- фактором и для матрицы, поскольку . Далее, весь набор базисных векторов Q- фактора QR разложения можно, в соответствмиеил- с ко блочным аналогом форму(л2ы.3) в терминах блчоных преобарзований Хаусхолдер,а вычислить по формуле . Очевидно имеет место равенство: , а также аналогично
, но тогда очевидно . Таким образом, базисные векторы профильн-огфоак-Q тора QR зрлаожения можно вычислять построив базисные векторы расширенного Q- фактора QR разлоежния и отбросив их первРыиес. 3. Заполнение Q фактора компоненты. Заметим, что первые компоненты расширенного базисного вектора нулевыеп,оскольку в противном случае после умножения на невны-рожде ную матрицу результирующий вектор будет ненулевым, что противоречит тождеству . В случае неполного столбцевого ранга эквивалентности нет, и это связано именно с тем, что в этом случае нтоеркыое начальные компоненты базисных векторов расширенногоу-QR б дут ненулевыми.
Исходя из описания расширеннопгроофильного QR разложения может сложиться впетч-а ление, чтоего Q- фактор всегда более заполн,енчем в исходномпрофильном разложении. В случаях, когда строится QR разложение матрицы, близкой к квадратзнаочйа,стуэютодействительно может быть так. Например, для ма,тризцоыбраженной на Рисунк,е Q-1 фактор ее расширенного профильного QR имеет вид, показанный на Рисун(октесо3единенная диагональ не показан)а, т.е,.действительно значительно более заполнчеенм тот, что показан на Рисунке 1. Тем не менее, даже для матриц, близких к квадратным, имеются примеры, когда заполнение расширенного профильного Q- фактора заметно меньшее. Это иммееестто, например, для тм-а рицы, изображеннойслева на Рисунке 4Р.ассмотрим вопрос о заполнении- фQактора QR зр-а ложения подробнее.
Рис. 4. Профильное (слева) и Q фактор расширепнрноофгоильного (справа) QR разложения Имеется достаточно простой способ определемнеиляко блочногозаполнения Q фактора в расширенном профильном QR. Будем предполагать извесмтнеолйко блочную структурмуатрицы . По этой структумроежно легко вычислить заполнение- фRактора QR разложения как результат символьнотйреугольной факторизации мелко блочнойструктуры . Но тогда очевидно без учета отсоединенной диагонамлиелко блочнаяструктура любого - го блочного преобразования Хаусхолдера при расширенной профильной факторизацеисить сумма стркутуры - го столбца плюс сумма структур предыдущбилхочных преобразований Хаусхолдера только для тех предыдущих индексов, для которых имеется соответствующий структурный элемент в н-аддиагональной части - го мелко блочногостолбца матрицы . Это следует из того простого факта, что в силу особенностей структуры расширенного профильноег-о разлож ния соответствующий элемент в структуре R при разложении может возникнуть только в этом случае. А большего взаимодействимяежду преобразованиямиХаусхолдера быть также нео-м жет, иначе при некоторычихсловых значениях будетиметь местодополнительное заполнение в R.В некотором смысле это наименьшее возможное заполпнрееноиберазований Хаусхолдера в под- диагональной частинеявного представленияQ- фактора. В частности, заполненибелочных преобразований Хаусхолдера в расширенном профильном разложении не зависиот- от уп рядочивания мелко блочныхстрок. Более того, для матрицы полного ранга очевидно структура разреженности любого блочного базисного вектора совпадает со структурсоойответствующего блочного преобразования Хаусхолдера для расширенного профильного QR (без учетиа- отсоед ненной диагонали). Для матрицы полного ранга имеет место еещтеесбноалясвязь с базиыснми блочными векторами Q- фактора: сам -й блочный вектор расширенного профильного QR имеет прямое отношение к-му базисному блоку направленQий- фактора. Тем не менее, мы не будем нигде явно использоваутьвозэмтожную связь, поскольку в приложениях о-пост янно приходится иметь дело атсримцами неполного рангаВ. случае осбычным профильным разложением заполнениеблочных преобразований Хаусхолдера Qв- факторе дополнительно порождается также возникающимелко блочнодиагональным структурным элеменмто, и-зза чего начинают взаимодействовьат те преобразования Хаусхолдера, которые могли быи-не вза модействовать в случае расширенного профильного разложения. Именно это взаимодействие через диагональный элемент и приводит к разнице заполнений на Рисунке 4.
Дополнительное заполнениеблочных преобразований Хаусхолдера -Qфактора в н-аддиагональной частирасширенного профильногоQR разложения может быть значительным, как это уже было показано выше. Тем не менее, в частном случае матриц с числоим- строк знач тельно превышающем число столбцов этдиомполнительным заполнением можно пренебречь на фоне возможного избыточного внутри профильного- дипаогдонального заполнения -изза взаимодействий преобразований Хаусхолдера на диагональном элементе. В контекстее- интер сующих автора приложений число столбвцсоевгда будет суммарно в сотни и тысячи ьр-аз мен ше числа строк, поэтому в последующей части изложения в качестве базового руа-зложения б дет использоваться только расширенное профильное QR разложение. Расшипрреонфниолеьное QR разложение имеет еще одно етсвтеенсное структурное преимущество. Если число строк в матрице меньше числа столбцо(вчто редко, но случается в приложени-язха, инзапример, дополнительного строчного биения матри)ц,ытов этом случаве профильном разложении жн-у но делать ч-ттоо искусственое, в то время как в расширенном разложении это не приводит к особым ситуация м. 4. QR разложение матрицы с заданным строчным биением Для прямоугольной матрицы
введем ее блочно строчное биение в виде: и ее QR разложение Обозначим
. Имеют место соотношения
где , , и . Пусть для каждой из матриц имеет местзо- QR ра
ложение типа2.(
. Очевидно, что вмелко блочнойразреженной матрице при введении ее строчного биения в строчнымхелко блочныхподматрицах может быть много нулевмыехлко блочных столбцов. Для их учета(4.2в) будем предполагать, что в кажпдоодйматрице имеется ровно ненулевых блочных столбцов, , , и что для каждпойдматрицы известна такаямелко блочная перестановка блочных столбцов , , что в матрице ровно первые блочных столбцов ненулевые.Пусть далее для матрицывычислено ее QR разложение вида с квадратной матрицей , тогда представление (4.2) получается из (4.3) неявным добавлением в произведении блочных множителей с единичной матрицей (частный случай блочного преобразования Хаусхолдера) ис квадратной матрицей вида: Заметим, что в контексте формулы (4.4) матрицва (4.2) не обязательно верхняя трье-угол ная. Обозначим .
Рассмотрим задачупостроения QR разложения всей матрицы4.1и)з н(а основе разложений (4.2). Для этого рассмотрим разреженную матрицу , (4.5) (4.6) , , (4.7) (4.8) где причем
. Отсюда следует, что неявное представлен8и)е со(в4м.естно с равенством из (4.7)есть QR разложение матриц ы,при этом матрица представляет собой -Q фактор QR разложенияа, квадратная верхняя треугольная матрицеасть R- фактор QR раозлжения.
Описанная конструкция очевидно позволяет параллельным образом вычислять Qо-R разл жение матрицы за счет введения строчного биения. Деелйьснтов,итстрочные QR разложения можно считать независимо. Синхронизация вычислений происходит только при вычислении объединяющего QR разложения (4.6). С другой стороны понятно, что подобный сп-одход к о новному распараллеливанию вычислений может быть эффенктитвоелько если число столбцов в матрице существенно меньше числа строк, иначе затраты на объединяющее QR разложение могут доминировать в вычислениях. 5. Верхняя квази- треугольная матрица с разреженностью типа вложенных сечений и параллельный алгоритм построения ее QR разложения
Описанный в предыдущем разделе параллельный алгоритм вычисления QR разложения по блочным строкам можно сделать эффективным за счет использдоовпаонлиняительной столбцевой разреженности матрицы.
Для начала рассмотрим д-вуухровневую организацию вычислений для прямоугольной матрицы со структурой разреженности, изображенной на Рисунке 5Пусслтеьва.число мелко блочных столбцов в матрицах, и равны соответственно , и соответственно, . Рис. 5. Двух- (слева) и тр-ех(справа) уровневая организация параллельного
вычисления QR разложения Действуя в духе предыдущего раздела вычибслоичмно строчныеQR разложения: .
(5.1) (5.2) (5.3) (5.4) В соответствии с (4.5) объединяющий QR нужно строить для матрицы Если в матрице переставить вторую и третью блочные строки, то получим мавтирдиац: у В первых двух круп- нболочных столбцах матрица уже треугольная, все блочные е- пр образования Хаусхолдера для них можно считать единичными матрицами, адлязнпаоч-ит строения объединяющего QR разложения достаточно вычислить QR разложение матрицы Существует множество способов, при помощи которыхежреназнрую прямоугольную мл-е ко блочную матрицу можно привести к виду многоуровневой верхней - ктвраезуигольной матрицы типа вложенных сечений. Простейший из них например такой.
По структуре разреженности матрицы вычисляем упорядочивание вложеннысхечений. Поструктуре переупорядоченной матрицы строим блочное биение и бинарное дерево нужной глубины, которое описывает разреженность этой матврикцоынтексте вложенныхе- с чений. Переупорядочивеам мелко блочные столбцы матрицыв соответствии с пуорядочиванием вложенных сечений. Упорядио-ч вание строк вводим последовательно нумеруя элементы первого мелко блочного столбца , затем второго и т.д. Столбцевео-е би ние вводим в сооттсвтевии с биением вложенных сечений. чС-тро ное биение вводим по мере ктаокго заканчиваются столбцевые блоки. В результате получитпсеяреупорядоченная по столбцам и строкам матрица с введеннымстрочным и столбцевым биением типа изображенной на Рисунке 6.
В некоторых случаях удобное- вв сти дополнительное строчное упя-ор Рис. 6. Упорядочивание и дочивание и биение для иомпитзации биение тестовой матрицы затрат при обработке окаймлений матрицы. Для этого в каждой блочной строке последними ставим строки, в котоырх есть лэементы в последнем окаймлении, и вводим новый строчный блок если такие строки есть; предпослесдтна-ими вим строки, которые не были перенесены в конец иракноетеорые Рис. 7. Дополнительное строч- имеются в предпоследнем окаймле н,иии ставимновый строчное упорядочивание и биение ный блок если такие стриомкиеются, и т.д. Для тестовой задачи на Рисунке 6 получится новое строчное упорядочивание и строчное биение, изображенное на РисункеНа7. рисунке видно заметно меньшее блочан-ое з полнение в окаймлениях матрицы. Для задачи в таком дополнительном биении построить QR разложение можно параллельным алгоритмом, аналогичным описанному выше. Допоь-лнител ным является этап объединяющего строчного QR разложения в рамках одного узал-а дерева з висимостей, которое возникает по причине введения дополнительного строчного бижен-ия в ка дой основной подматрице. 6. Построение упорядочиваний и биений ND-типа на основе объемного биения расчетной сетки на домены
Описанный в предыдущем разделе основанныйявнноам вычисленииупорядочивании ND способ построения упорядочиваний и биений, прирыкхотомелко блочная матрица становится многоуровневой верхней ква-зитреугольной типа вложенных сечений, не является практически удобным для множества приложений, в которых матрица возкнаиккаселтедствиеаппроксимации уравнений на расчетной сетке. Для пноыдхобзадач необходиамспециальная методика опстроения соответствующих упорядочиваний и биений. В данном разделе предлагаебт-ся подо ная методика, которая основана на предположении о том, что истсотлрбоцкыиматрицы асосциируются естественным образом с элетмамени расчетной сетки, и для этой сетки имеется ее геометрически локальное разбиение на достаточно малые об-ъдеоммыены.
Таким образом, предположи, мчто для расчетной области имеется разбиение на домены, и
что строки и столбцы матрицы ассоциируются стнырамсиче доменами. Это означает, чтзо- во
можно ввести нумерацию доменов, нумерацию строк и столбцов матрицы и строчбн- ое и стол
цевое биения таким образом, чтобы в общем случае в прямоугольном блоке (
Для начала рассмотрим вопрос о построении дерева зависимостей вычислений. Для этого введем в рассмотрение две квадратных разреженных целочисленных матрицы размер,ом здесь - полное число домен.ов Первую матрицу будем назывмаатьтрицей вязей. В этой матрице в каждой строке есть элтеыментолько на диагоналит,акаже в тех позициях , в которых есть хоть один структурный элемент в блоке связи -тмыемждиу -тым домнеами. Вторую целочисленную матрицу будем назывмааттьрицей ве ов. Ее структура разреженности совпадает со структурой разреженности матрицы связей. Диагональные элеммаетнртиыцы весов содержат число элементов геометрии в домене (число ячеек-)д,иаговннаельный элемент в позиции содержит полное число элементов в блояк-е св зи между -тым и -тым доменами. По мраитцам связей и е-в сов рекурсивно проводим биение всей расчетной области на две большие подобласти, каждый раз содержащие близбк-ое о щее количество элементов геометрии (ячеек сетки) и имеющие минимальное количество связей межэдтуими двумя подоба-л стями. Это бнииее продолжается рекурсивно до тех пор, пока в подобласти имеется более одногоомедна. Таким образовмозРис. 8. Нумерация узлов дерева никает представлениенабора доменов в видкевази- бинарного дерева. Пусть - число уровней этого кв-азбиинарного деерва. Все домены являются листьями отноеркого уровня дерева. Построенное к-вабзиинарное дерево и будем считать требуемы-муровневым деревом зависимостей вычисленийУ.порядочим узлы дерева зависимостей таким образом, чтобы каждый узел дерева имеющий сыновей имел номер не меньший, чем номера всоевхпоудздлеревьев этого узла. Такое упорядочивание номеров узлов дерева очевиднуощесствует. На Рисунке 8 показана нумерация узлотврехд-ля уровневого бинарного дерева.
Для окончательного построения упорядочиваний матрицы, ее строчного и столбцевого биений рассмотрим подробнее структуру каждого домена (двумерный пример привеид-ен на Р сунке 9).
Рис. 9. Геометрическое разбиение двумерного домена на подобласти В каждом домене выберемтакой набор его геометрических элементов, который не имеет связей с внешними геометрическими элементами (подобласть 0 на 9Р)и, сувнкетерминах-х 3 мерных задачназовем его объемной внутренней частью до.мИезнаоставшихся элементово- д мена выделим связные подобласти геометрических элементов, связанных ровно с ошд-ним вне ним доменом (подоблаист1-4 на Рисунке9), в терминах-х 3 мерных задач назовем эти бп-одо ласти квази- поверхностными (квази- двумерными) границами домена. Далее из оставшихся геометрических элементов домена выделим связные подобласти геометрических элементов, связанные ровно сдвумя внешними доменами (подобласти 5-8 на Рисунке9), в терминах-х 3 мерных задач назовем эти подоблиасктвази- одномерными границами домена.Для не менее чем трехмерных задач далее из оставшихся геометрических элементов выделим пос-вязные добласти геометрических элементов, связанных робвонлоее чем с двумя внешними доменами, в треминах трехмерных мерных задач назовем эти подобилаксвтази нуль- мерными границами домена. Упорядочим матрицу в соответствии с введенным биеиниуемпорядоченным ква-зибинарным деревом зависимостей следующим обр.азДолмя этого введем соответствие межзд-у у лами дерева и введенниымновымистрочным и столбцевым блочниымбиениями. Поместим каждый столбцевой блок в соответствии с его ссвляездяумюищим образо м. Внутренние стоблцевые блокидомена поместим в соответствующидйомену лист дерева. Столбцевые квази хдву мерные границы всех доменов поместим в наименьший по номеру узел упорядоченного дерева зависимостей, в сыновьях которого имеются узлы дерева, содержащие соответствуюищ-ие род тельские для этой квадзвиух мернойграницы 2 домена. Аналогично, столбцевые квази -одно мерные границы всех доменов поместим в наименьший по номеру узел упорядоченного дерева зависимостей, в сыновьях которого имеются узлы дерева, содержащие соответствуюищ-ие род тельские для этокйвази одномерной гарницы 3 домена. Наконец, остальные столбцевые квази нуль- мерные границы всех доменов поместим в наименьший по номеру узел упорядоченного дерева зависимостей, в сыновьях которого имеювстесяузлы дерева, содержащие соотвте-тс вующие родительские для этковйази- нульмерной границы >3 доменов. Строчные подблоки каждого домена разместим в тех узлах упорядоченного дерева зависимостей, в котором они встречаются в первый ,реасзли блочные столбцызаранее упорядочитьв соответствии с ио-п санным выше алгоритмом. Да,леевсе блочные столбцы в каждом узле упорядочим рп-о их ме ности - чем больше мерность, тем раньше расположен столбцевой блок. После подео-бных пр образований очевидно матрица станет- уровневой верхней ква-зитреугольной матрицей типа вложенных сечений, ие еструктура разреженности будет иметь вид, подобный изображенному на Рисунке 7Д.ля уменьшения заполнения- иQ R- факторов QR разложений в столбцевыох- бл ках узлов можно дополнительно использовать упорядочивание ND как было описано выше. Заключение
В работепредставлен параллельный алгоритм вычисления QR разложменоигяоуровневой разреженной верхней ква-зитреугольной матрицысо структурой разреженносттиипа вложненых сечений. Базовым вычислительным примитивом алгоритма являются блочные нр-азреже ные преобразования Хаусхолдера.Предложены варианты алгоритмов, приводящих заданную матрицу к упомянутому виду, удобному для параллельного вычисления ее разреженного QR разложения, в том числе для задач аппроксимации уравнений на расчетнРоейзулсьеттактеы. численных кэспериментов с предложенным алгоритмом для тестовых задгаичбринданой параллельной MPI+threads+SIMD архитектурпериведены в работе 6][, также представленной в качестве доклада на конференц.ию Литература (1998). женных сечений// Представлена вачекстве доклада на первуоюбъединенную международную конференцию "Суперкомпьютерные дни в РоссиМи"о,сква, 28-29 сентября 2015 г. 7. Haidar A., Dong T., Tomov S., Luszczek P., Dongarra J. Framework for Batched and GPUresident Factorization Algorithms Applied to Block Householder Transformations. Parallel algorithm for sparse QR decomposition of a rectangular upper quasi triangular matrix with ND-type sparsity Sergey Kharchenko Keywords: sparse rectangular matrix, upper quasi triangular matrix, nested dissection, volume partitioning, QR decomposition, Householder transformations, parallel algorithm, SLAE, least squares problem The paper considers algorithm for computing sparse QR decomposition of a specially ordered rectangular matrix. Decomposition is based on block sparse Householder transformations. For ordering computations the ND-type ordering for sparsity of ATA matrix can be used, here A original rectangular matrix. For mesh based problems the ordering can be constructed starting from appropriate volume partitioning of the computational mesh. Parallel computations are based on sparse QR decomposition for sets of rows with additional zero block at the beginning. The suggested algorithm is planned to be used as main computational kernel in the developed by the author parallel iterative algorithms for solving SLAEs and least squares problems. The corresponding algorithms will be based on composition of the subspaces represented by sparse bases.