Предобуславливание разреженных матриц с помощью попеременных и мультипликативных операторных разложений

Представлена алгебраическая структура для предобуславливающих схем на основе операторных разложений для общих разреженных матриц. Эта структура приводит к четырем различным подходам: двум на основе попеременных разложений и двум на основе мультипликативного анзаца. Анзац обобщает методы попеременного неявного направления (ADI) и неполного LU-разложения (ILU) на случай нескольких факторов и на более общую форму факторов. Факторы могут вычисляться напрямую из коэффициентов матрицы или адаптивно с помощью неполных разреженных инверсий. Особый случай тридиагональных разложений рассматривается детальнее: мы разлагаем граф смежности разреженной матрицы на несколько (почти) несвязных линейных лесов, где каждый линейный лес (объединение несвязных путей) задает тридиагональное разложение. Из этой конструкции получаются специализированные варианты четырех общих подходов. Для всех этапов реализованы параллельные реализации на GPU. Показана эффективность и производительность этих предобуславливателей в сочетании с GMRES на наборе матриц.