ALGEBRAIC ALGORITHMS AND NUMERICAL ALGORITHMS

代数算法和数值算法

• 批准号: 10680357
• 负责人: LI Lei
• 金额: $ 1.86万
• 依托单位: YAMAGUCHI UNIVERSITY
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10680357/
• 关键词: ALGORITHM; FAST; PARALLEL; COMPUTATIONAL COMPLEXITY; VANDERMONDE; P-MATRIX; H-MATRIX; LCP; P-Matrices; Matrix; 行列; 収束性; 計算複雑さ; H行列; 並列処理

In this project, we have researched design and analysis of algebraic algorithms and numerical algorithms for scientific computation. Connection of the algebraic and numerical algorithms, and the upper bounds of some computational complexities became clear. We have got the following research results in collaboration with some overseas researchers. Put emphasis on H-matrices, we found many practical distinguishing conditions for convergence of the algorithms and stabilities of control systems, and proposed a fast algorithm for finding the trigonometric sums which are often appeared in signal processing. An approximate parallel solution of integral equation for radiative heat exchange and a parallel algorithm for solving the implicit defusion deference equations was proposed separately. The time complexity for testing whether an n-by-n real matrix is a P-matrix is reduced from O(2^n n^3) to O(2^n) by applying recursively a criterion for P-matrices based on Schur complementation. A Matlab program implementing the associated algorithm is provided. We also presented some new fast algorithms for solving an norder Vandermonde linear system of equations, and Vandermonde determinants. The arithmetic operational complexity of these algorithms will be not more than O(n logn^2). This research also proposed an O(n^3) recursive algorithm for solving the LCP (A, q) with A is an M-matrix.

在这个项目中，我们研究了科学计算的代数算法和数值算法的设计和分析。代数和数值算法的联系以及某些计算复杂性的上限变得清晰。我们与一些海外研究人员合作取得了以下研究成果。我们以H矩阵为重点，发现了算法收敛性和控制系统稳定性的许多实际区别条件，并提出了一种求信号处理中经常出现的三角和的快速算法。分别提出了辐射换热积分方程的近似并行解法和隐式解聚偏差方程的并行求解算法。通过递归应用基于 Schur 补集的 P 矩阵标准，测试 n×n 实数矩阵是否为 P 矩阵的时间复杂度从 O(2^n n^3) 降低到 O(2^n) 。提供了实现相关算法的 Matlab 程序。我们还提出了一些新的快速算法，用于求解阶范德蒙线性方程组和范德蒙行列式。这些算法的算术运算复杂度不会超过O(n logn^2)。这项研究还提出了一种 O(n^3) 递归算法来求解 LCP (A, q)，其中 A 是 M 矩阵。

项目成果

谷萩,李 他: "高速アルゴリズムと並列信号処理"コロナ社. 254 (2000)

Tanihagi, Lee 等人：“高速算法和并行信号处理”Corona Publishing 254 (2000)。

Lei Li: "On the Arithmetic Operational Complexity for Solving Vandermonde Linear Equations"Japan J. of Indus. & Appl.Math.. 17・1. 15-18 (2000)

李雷：“论求解范德蒙线性方程组的算术运算复杂性”Japan J. of Indus & Appl.Math. 17・1 (2000)

L.Li, T.Nakamura: "Fast Parallel Algorithms for Vandermonde Determinants"Inter.J.of Computer Math.. 73. 479-486 (2000)

L.Li, T.Nakamura：“Vandermonde 行列式的快速并行算法”Inter.J.of Computer Math.. 73. 479-486 (2000)

H.Yahagi, L.Li etc: "Fast Algorithms and Parallel Signal Processing"Korona Publishing. 1-254 (2000)

H.Yahagi、L.Li 等：《快速算法和并行信号处理》Korona 出版社。

Lei Li,T.Nakamura: "Fast Parallel Algorithms for Vandermonde DET"Inter.J.of computer Math.. 73・4. 不-明 (1999)

Lei Li, T. Nakamura：“Vandermonde DET 的快速并行算法”Inter.J.of 计算机数学.. 73・4 未知 (1999)