Нелинейные аппроксимации матриц
Диссертация
Таким образом, эффективные алгоритмы могут быть основаны на нелинейных малопараметрических аппроксимациях матриц. Однако далеко не всегда очевидно, как получить эффективное малопараметрическое представление матрицы. Более того, чтобы быстро работать с такими структурами, мы должны уметь выполнять матричные операции (сложение, умножение, обращение) именно в терминах малопараметрического… Читать ещё >
Содержание
- 1. 1. Нелинейные аппроксимации матриц: зачем и как
- 1. 3. Содержание работы по главам
- 1. 1. Введение
- 1. 2. Задачи С+Я и Б+К аппроксимации
- 1. 3. Чёрные точки, малые ранги и скелетоны
- 1. 4. Адаптивная версия метода чёрных точек
- 1. 5. Тёплицев случай
- 1. 5. 1. Быстрое вычисление образа Фурье для тёплицевой матрицы
- 1. 6. Существование С+Я аппроксимации для некоторых классов тёплицевых матриц
- 1. 7. Численные эксперименты
- 1. 8. Метод чёрных точек для произвольного шаблона
- 1. 9. Неизвестный шаблон
- 1.
- 2. 1. Введение
- 2. 2. Основные понятия и определения
- 2. 3. Вейвлет-пространство. Масштабирующие и лифтинговые коэффициенты
- 2. 4. Основная система
- 2. 5. Решение основной системы
- 2. 6. Нахождение масштабирующих коэффициентов
- 2. 7. Алгоритм вычисления вейвлет-преобразования
- 2. 8. Численные эксперименты
- 2. 8. 1. Пример
- 2. 8. 2. Пример
- 2. 9. Выводы
- 3. 1. Введение
- 3. 2. Масштабированные циркулянтные предобуславливатели
- 3. 3. Приближённое обращение структурированных матриц
- 3. 4. Методы построения приближённой обратной матрицы
- 3. 4. 1. Метод Ньютона с аппроксимациями
- 3. 4. 2. Модифицированный метод Ньютона
- 3. 5. Численные результаты
- 3. 5. 1. Масштабированный циркулянтный преобуслав-ливатель
- 3. 5. 2. Предобуславливатели на основе метода Ньютона
- 3. 6. Выводы
- 4. 1. Введение
- 4. 2. TDS формат
- 4. 3. Арифметика TDS формата
- 4. 3. 1. Основные арифметические операции
- 4. 4. Основные арифметические операции в тензорном формате
- 4. 4. 1. TDS-рекомпрессия
- 4. 4. 2. Оператор обрезания
- 4. 5. Метод Ньютона и выбор начального приближения
- 4. 6. Численные результаты
- 4. 7. Структура обратных к двухуровневым матрицам специального вида
- 4. 7. 1. Так почему же 5?
- 4. 7. 2. Обобщение на случай большего числа слагаемых
- 4. 8. Выводы
Список литературы
- М. Bebendorf, Approximation of boundary element matrices, Numer. Math., 2000, 86, 565−589.
- M. Bebendorf and S. Rjasanow, Adaptive low-rank approximation of collocation matrices, Computing, 2003, 70, 1−24.
- M. Bebendorf, S. Rjasanow and Б. Б. Tyrtyshnikov, Approximation using diagonal-plus-skeleton matrices, Math. asp. of bound, elem. meth. (Palaiseau, 1998), Chapman Hall/CRC, Boca Raton, FL, 2000, 45−52.
- R. Chan, Circulant preconditioners for Hermitian Toeplitz systems, Linear Algebra Appl., 1989, 10, 542−550.
- T. F. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput., 1988, 9, 766−771.
- R. H. Chan, D. Potts, G. Steidl, Preconditioners for Nondefinite Hermitian Toeplitz Systems, SIAM Matrix Anal. Appl, 2001, 22:3, 647−665.
- R. H. Chan, M. K. Ng and A. M. Yip, A Survey of Preconditioners for 111-Conditioned Toeplitz Systems, Structured Matrices in Mathematics, Computer Science, and Engineering II, Contemporary Mathematics, 2001, 281, 175−191.
- I. Daubechies. Orthonormal bases of compactly supported wavelets. Communications of Pure and Applied Mathematics, October 1988, 41:7, 909−996.
- B. W. Dickinson, Solution of linear equations with rational Toeplitz matrices, Math. Comput., 1980, 34:149, 227−233.
- T. A. Driscoll and B. Fornberg, A Padie-based algorithm for overcoming the Gibbs phenomenon, Numerical Algorithms, 2001, 26, 77−92.
- J. M. Ford, E. E. Tyrtyshnikov, Combining Kronecker product approximation with discrete wavelet transforms to solve dense, function-related systems, SI AM J. Sci. Comp., 2003, 25:3, 961−981.
- I. Gohberg, G. Heinig, Inversion of finite-section Toeplitz matrices consisting of elements of a non-commutative algebra, Rev. Roum. Math. Pures et Appl, 1974, 19:5, 623−663.
- S. A. Goreinov, E. E. Tyrtyshnikov, The maximal-volume concept in approximation by low-rank matrices, Contemporary Mathematics, 2001, 208, 47−51.
- S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, A theory of pseudo-skeleton approximations, Linear Algebra Appl, 1997, 261, 1−21.
- W. Hackbusch, A sparse matrix arithmetic based on 7i -matrices. I. Introduction to H-matrices, Computing, 1999, 62:89−108.
- W. Hackbusch, B. N. Khoromskii, A sparse H-matrix arithmetic. II. Application to multi-dimensional problems, Computing, 2000, 64, 21−47.
- W. Hackbusch, B. N. Khoromskii, E. E. Tyrtyshnikov, Hierarchical Kronecker tensor-product approximations, Max-Panck-Institut fur Mathematik in den Naturwissenschaften, Leipzig, Preprint No. 35, 2003.
- W. Hackbusch, Z. P. Nowak, On the fast matrix multiplication in the boundary elements method by panel clustering, Numer. Math., 1989, 54:4, 463−491.
- G. Heinig, K. Rost, Algebraic methods for Toeplitz-like matrices and operators, Berlin, Academie-Verlag, 1984.
- H. Hotelling, Analysis of a complex of statistical variables into principal components, J. Educ. Psych., 1933, 24, P I: 417−441, P II: 498−520.
- T. Kailath, S. Kung, M. Morf, Displacement ranks of matrcies and linear equations, J. Math. Anal. and Appl, 1979, 68, 395−407.
- J. Kamm, J. G. Nagy, Optimal Kronecker Product Approximations of Block Toeplitz Matrices, SIAM J. Matrix Anal Appl., 2000, 22:1, 155−172.
- T.-K. Ku, C.-C. J. Kuo, Spectral properties of preconditioned rational Toeplitz matrices: the nonsymmetric case, SIAM J. Matrix Anal. Appl., 1993, 14:2, 512−544.
- D. Noutsos, S. Serra Capizzano, P. Vassalos, A preconditioning proposal for ill-conditioned Hermitian two-level Toeplitz systems, Numer. Linear Algebra Appl, 2005, 12, 231−239.
- V. Rokhlin, Rapid solution of integral equations of classical potential theory, J. Comput. Physics, 1985, 60, 187−207.
- Y. Saad, Iterative Methods for Sparse Linear Systems, PWS Publishing Company, An International Thomson Publishing Company, Boston, 1996.
- L. Schumaker, Spline functions: basic theory, Wiley, New York, 1981.
- G. Schulz, Iterative Berechnung der reziproken Matrix, Z. angew. Math, und Mech., 1933, 13:1, 57−59.
- G. Strang, A proposal for Toeplitz matrix calculations, Studies in Applied Mathematics, 1989, 84, 171−176
- V.V.Strela and E.E.Tyrtyshnikov, Which circulant preconditioner is better? Math. Comput., 1996, 65:213, 137−150.
- W. Sweldens, The lifting scheme: A custom design construction of biorthogonal wavelets, Appl Comput. Harmon. Anal, 1996, 3, 186 200.
- W. F. Trench, An algorithm for the inversion of finite Toeplitz matrices, SIAM J. Appl Math., 1964, 12, 515−521.
- E. E. Tyrtyshnikov, Kronecker-product approximations for some function-related matrices, Linear Algebra Appl, 2004, 379, 423−437.
- Е. Е. Tyrtyshnikov, Optimal and superoptimal circulant preconditioners, SI AM J. Matrix Anal. Appl, 1992, 13:2, 459−473.
- E. E. Tyrtyshnikov, Incomplete cross approximation in the mosaic-skeleton method, Computing, 2000, 64:4, 367−380.
- E. E. Tyrtyshnikov, A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl., 1996, 232, 1−43.
- E. E. Tyrtyshnikov, Mosaic-skeleton approximations. Calcolo, 1996, 33:(l-2), 47−57.
- E. E. Tyrtyshnikov, R. Chan, Spectral Equivalence and Proper Clusters for Boundary Element Method Matrices, Int. J. Numer. Meth. Engnr., 2000, 49, 1211−1224.
- E. E. Tyrtyshnikov, N. L. Zamarashkin, and A. Yu. Yeremin, Clusters, preconditioners, convergence, Linear Algebra Appl., 1997, 263, 2548.
- C. F. Van Loan, N. P. Pitsianis, Approximation with Kronecker products, NATO Adv. Sci. Ser. E Appl. Sci., 1993, 232, 293−314.
- N. Yarvin, V. Rokhlin, Generalized Gaussian quadratures and singular value decompositions of integral operators, SIAM J. Sci. Comput, 1999 20:2, 699−718.
- A.А. Акопян, А. А. Саакян. Многомерные сплайны и полиномиальная интреполяция. Успехи математических наук, 1993, 48:5.
- С. М. Белоцерковский, И. К. Лифанов, Численные методы в сингулярных интегральных уравнениях, М., Наука, 1985.
- B.А. Василенко Сплайн-функции: теория, алгоритмы, программы, Новосибирск: Наука, 1983. 216 с.
- B. В. Воеводин, Е. Е. Тыртышников, Вычислительные процессы с теплицевыми матрицами, М., Наука, 1987.
- C. А. Горейнов, Н. Л. Замарашкин, Е. Е. Тыртышников, Псевдоскелетные аппроксимации матриц, ДАН, 1995, 343:2, 151−152, 1995.
- И. Ц. Гохберг, А. А. Семенцул, Об обращении конечных тёплице-вых матриц и их непрерывных аналогов, Матем. исслед., 1972, 7:2, 201−224.
- И. Добеши. Десять лекций по вейвлетам, Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001
- С. А. Довгий, И. К. Лифанов, Методы решения интегральных уравнений, Наукова Думка, Киев, 2002.
- И. К. Лифанов, Б. Е. Тыртышников, Теплицевы матрицы и сингулярные интегральные уравнения, Вычислительные процессы и системы, Вып. 7, 94−278. М., Наука, 1990.
- И. К. Лифанов, Л. Н. Полтавский, Обобщенные операторы Фурье и их применение к обоснованию некоторых численных методов в аэродинамике, Матем. сб., 1992, 5, 79−114.
- Е. Е. Тыртышников, Тензорные аппроксимации матриц, порожденных асимптотически гладкими функциями, Матем. сб., 2003, 194:6, 147−160.
- Е. Е. Тыртышников, Методы быстрого умножения и решение уравнений, Матричные методы и вычисления, ИВМ РАН, Москва, 1999, 4−41.
- Е. Е. Тыртышников, Тензорные аппроксимации матриц, порожденных асимптотически гладкими функциями, Матем. сб., 2003, 194:6, 147−160
- Д. К. Фаддеев, В. Н. Фаддеева, Вычислительные методы линейной алгебры, М.-Л., Физматгиз, 1963.
- К. Чуй. Введение в вейвлеты, Москва, «Мир», 2001
- Публикации по теме диссертации
- V. Olshevsky, I. Oseledets, Е. Tyrtyshnikov, Tensor properties of multilevel Toeplitz and related matrices, Linear Algebra Appl., 2006, 412, 1−21.
- Oseledets I.V., Tyrtyshnikov E.E., A unifying approach to the construction of circulant preconditioners, Linear Algebra Appt., 2007, 418, 435−449.
- Оселедец И.В., Тыртышников Е. Е., Приближённое обращение матриц при численном решении гиперсингулярного интегрального уравнения ЖВМ и МФ, 2005, 45:2, 315−326.
- Оселедец И.В., Применение разделённых разностей и В-сплайнов для построени быстрых дискретных преобразований вейвлетов-ского типа на неравномерных сетках, Мат. заметки, 2005, 75:5, 743−752
- Замарашкин H.A., Оселедец И. В., Тыртышников Е. Е., О приближении тёплицевых матриц суммой циркулянта и матрицы малого ранга, ДАН, 2006, 73, 100−101.
- Ford J. М., Oseledets I. V., Tyrtyshnikov E. E., Matrix approximations and solvers using tensor products and non-standard wavelet transforms related to irregular grids, Rus. J. Numer. Anal, and Math. Modelling, 2004, 19:2, 185−204.
- Оселедец И.В., Оценки снизу для сепарабельных аппроксимаций ядра Гильберта, Матем. сб., 2007, 198:3, 137−144.
- Оселедец И.В., Савостьянов Д. В., Ставцев С. Л., Применение нелинейных методов аппроксимации для быстрого решения задачи о распространении звука в мелком море. Методы и технологии решения больших задач, ИВМ РАН, 2004, 171−192.