实对称Toeplitz矩阵与向量的乘积的快速算法

摘要

矩阵向量积是数值代数中一种基本运算，传统的算法需要O(n2)浮点运算。本文研究实对称Toeplitz矩阵与实向量积的快速算法。众所周知，Toeplitz矩阵在科学和工程计算中广泛应用。一个n阶的Toeplitz矩阵向量积的经典快速算法是首先将Toeplitz矩阵嵌入到一个2n阶的循环矩阵，然后利用3个离散Fourier变换(DFT)来实现，一个DFT的计算复杂度是10nlogn复运算，总体复杂度为30nlogn复运算。对于实对称Toeplitz矩阵向量积，当然可以用FFT去计算，但需要进行复数运算，相当于把问题复杂化。
　　为了避免了复数运算，本文研究了用离散余弦变换（DCT）和离散正弦变换（DST）来计算Toeplitz矩阵与向量的乘积，并分析了其复杂度。
　　本文结构共分为五部分，如下：
　　第一章、介绍了本课题的研究背景和现状，研究内容以及本文的创新工作。
　　第二章、介绍本文中涉及到的一些定义、性质和快速傅立叶变换（FFT）以及用FFT计算Toepliz矩阵与向量的乘积的算法。
　　第三章、介绍DCT和DST的定义和性质。
　　第四章、实对称矩阵与实向量的快速算法的实现，并分析其复杂度。
　　第五章、总结与展望。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景及现状

1.2 本文的创新方法

第二章 预备知识

2.1 相关定义的介绍

2.2 FFT的介绍

第三章 关于DCT和DST的介绍

3.1 DCT和DST的定义

3.1.1 DCT的定义

3.1.2 DST的定义

3.2 DCT和DST的性质

第四章 实对称Toeplitz矩阵与实向量乘积的快速算法

4.1 一般Toeplitz矩阵与向量乘积的快速算法

4.2 实对称Toeplitz矩阵与DCT和DST的关系

4.3 实对称Toeplitz矩阵与实向量乘积的快速算法

4.4 算法复杂度分析

第五章 总结与展望

参考文献

致谢

附录（攻读学位期间发表的论文）