"Записки научных семинаров ПОМИ"

Том 405, стр. 127-132

Московский государственный университет, ГСП-1, Ленинские горы, 119991 Москва, Россия

ikramov@cs.msu.su

Аннотация: Квазитеплицевой мы называем матрицу, в которой элементы квадрата, образованного позициями $(i,j), (i - 1,j), (i,j - 1)$ и $(i - 1,j - 1)$, связаны линейным соотношением с коэффициентами, не зависящими от $i$ и $j$. Показано, что система линейных уравнений с квазитеплицевой $n\times n$-матрицей коэффициентов может быть решена с затратой $O(n^2)$ арифметических операций. Библ. -- 2 назв.
Ключевые слова: теплицева матрица, матрица Паскаля, быстрые алгоритмы решения теплицевых систем [Toeplitz matrix, Pascal matrix, fast algorithms for solving Toeplitz systems]