Toeplitz系统在科学和工程计算中应用非常广泛，如信号处理中反馈数字滤波器的滤波系数、阵列天线的雷达散射截面分析、时间序列分析中固定自返模式的未知参数、控制论中的最小实现问题等都离不开Toeplitz系统的求解。 Toeplitz系统求解的算法主要是预条件共轭梯度法和多重网格法，前者的关键在于选择合适的预条件矩阵，对于后者，延拓算子和限制算子的选取对多重网格法的收敛速度有着重要的影响。因此，研究Toeplitz系统的预处理技术，即预条件矩阵的构造及延拓算子或限制算子的选取技术，已经成为Toeplitz系统求解问题中的研究热点。 目前，分布式存储并行处理机系统已经成为许多科学和工程的计算环境，成为求解重大挑战性问题的首选工具。因而，研究和设计Toeplitz系统在分布式存储环境下高效率的并行求解算法，将具有重要的理论意义和实际意义。 在如上的研究背景下，本文主要完成了如下工作： 1．扩展了预条件矩阵的构造空间。给出了基于正弦变换的交叉对角化预条件矩阵的构造空间，证明了已有正弦变换基预条件矩阵的构造空间是新的构造空间的子空间。在满足Frobines范数最小的意义下，给出了新的构造空间中最优预条件矩阵的构造方法。和已有预条件矩阵相比，构造新的交叉对角化预条件矩阵并没有增加计算量。在高性能计算机上的数值实验表明，新的预条件矩阵的特征值性能要优于传统预条件矩阵，且当应用于具体的Toeplitz方程组的求解时，新的预条件矩阵是有效的。 2．提出了结合小波变换技术和多重网格法求解病态Toeplitz系统的新思想。通过研究多重网格法，揭示了多重网格法中限制算子／延拓算子与小波滤波器中低通滤波器／高通滤波器间的关系。此后根据双正交小波的性质，提出了一种双正交小波的新型提升格式，作为数例构造了一种双正交紧支撑9／11小波。在此基础上，构造了新的限制算子和延拓算子以提高计算速度。测试结果表明，在应用于具体的病态Toeplitz系统求解时，新算法是有效可行的。 3．对三对角Toeplitz系统的并行求解问题，提出了两种基于系数矩阵不同分解的并行算法。一种是基于系数矩阵的完全LU分解，另一种是基于系数矩阵的近似LU分解，两种算法都充分利用了系数矩阵的特殊结构，并采用秦九韶算法避免了冗余运算，具有很好的内在并行性。算法的并行性能分析表明，两种基于不同分解技术的并行算法在分布式环境下均可以达到线性加速比，并且当n→∞时，加速比S_p→p。在某高性能分布式并行国防科学技术大学研究生院学位论文计算机上的数值实验获得了很好的线性加速比和并行效率。 4.对近似三对角ToePlitz系统的求解问题，提出了一个快速分布式并行算法。首先利用系数矩阵的特殊结构，对系数矩阵进行分解，利用分解后的结构考察系数矩阵的可逆性，推导出了求解该系统的快速算法，该算法也是目前求解近似三对角ToePlltz系统的最快的串行算法。通过分析算法的内在并行性，并结合秦九韶算法来避免冗余运算，提出了一种适合于分布式环境的快速并行算法。算法的并行性能分析也表明，在分布式环境下该算法可以达到线性加速比，并且当。分‘时，加速比S，分p。在某高性能分布式并行计算机上的数值实验同样获得了很好的线性加速比和并行效率。 5.对结合预处理技术的并行算法在信号处理中的具体应用，主要做了如下两部分的工作: (l)在采用预条件共扼梯度法的基础上，分别结合正弦变换基预条件矩阵和Harte加变换基预条件矩阵，对非均匀采样信号的重构问题，提出了两个新的重构算法。通过分析算法的内在并行性及在某分布式并行计算机上的数值实验，可以证明:两个结合并行处理技术的新算法的性能较为接近，都可以达到线性加速比，并且和己有算法相比，两种新算法的误差更小，重构精度更高，适用范围更广。 (2)给出了离散双正交小波的构造方法，在此基础上构造了新的限制算子和延拓算子。利用前面提出的结合多重网格法和小波变换技术求解病态ToePhtz系统的思想，提出了病态信号重构的新算法。通过分析算法的内在并行性及在某分布式并行计算机上的数值实验，可以证明:对于许多现有算法低效重构或无效重构的病态信号，结合并行处理技术的新算法可以实现有效重构，且可以达到线性加速比。关键词:ToePlitz系统，预条件共扼梯度法，预条件矩阵，正弦变换，多重网格法， 小波变换，并行算法，信号重构第11页