解非线性方程组的一类Krawczyk—Moore算法

在解非线性方程组的区间方法中,Krawczyk-Moore算法(K-M算法)是一类比较有效的方法。本文在K-M算法中以及Pandian推广的K-M算法中引进积分型区间扩张,从理论上证明了这类区间扩张使K-M算法在检验非线性方程组解的存在性、唯一性以及构造区间迭代的收敛性等方面更为有效;数值结果也给予充分说明。

一种串匹配的快速Boyer-Moore算法

在对经典的Boyer-Moore和Quick Search串匹配算法进行分析的基础上,提出了一种更加快速的串匹配算法Quick Boyer-Moore(QBM)。QBM算法利用当前尝试中的已匹配子串、匹配失败字符信息以及与当前窗口下一个字符的位置信息,以在每一次跳跃中获得更大的跳跃距离,从而使算法具有更高的效率。在真实语料上的实验结果表明,QBM算法的效率较显著地高于原始的BM算法及其改进算法Improved Boyer-Moore(IBM)。

Boyer-Moore串匹配算法的改进

在分析Boyer-Moore(BM)算法的基础上,提出了BM算法的一个新的变形。其基本思想是在算法的预处理阶段,对扩展模式串Pa建立好后缀规则,其中:P是模式串,a是字母表中的任一字符,既加大了已匹配后缀的长度,同时隐含了Sunday算法的坏字符规则,从而获得更大的窗口跳跃距离。理论分析证明,该算法具有线性最差时间复杂度和亚线性平均时间复杂度,空间复杂度为O(m(σ+1))。实验结果表明,该算法的实际性能与BM算法相比有明显改善,尤其适合小字母表的情形。

o-对称矩阵的正交对角分解及Moore-Penrose逆

研究具有轴对称结构的o-对称矩阵的正交对角分解和Moore-Penrose逆,给出了正交对角分解公式及Moore-Penrose逆的快速算法,据此可极大节省计算该类矩阵正交对角分解及Moore-Penrose逆时的计算量和存储量.

行满秩Toeplitz型矩阵Moore-Penrose逆的快速算法

通过构造对称分块矩阵给出了秩为m的m×n阶Toeplitz型矩阵Moore-Penrose逆的快速算法。该算法计算复杂度为O(mn)+O(m2),而由T(TTTT)-1直接求解所需运算量为O(m2n)+O(m3)。数值算例表明了该快速算法的有效性。

一种改进Boyer-Moore算法效率的预处理算法

通过理论分析和测试发现,对大多数字符串而言,按某个方向搜索文本总是会比按另一个方向的搜索速度快.提出了新的预处理算法,在使用Boyer-Moore算法之前先确定一个较优的搜索方向,其时间复杂度和空间复杂度分别为O(σm)和O(σ+m),其中σ和m分别为字母表的大小和字符串图案的长度.采用真实的人类DNA序列测试,包括序列库中前1 000个长度超过1 000的完整序列作为文本,从中随机选出1 000个长度为20的序列片段作为图案,进行实验对比,证明可以将搜索时间平均缩短到原来的约90%.

BWT-Boyer-Moore压缩域搜索算法的研究

针对Boyer-Moore匹配算法对压缩文本文件搜索的不足,分析了当前对于压缩文件搜索的主要方法,提出了一种基于BW转换的高效的搜索算法并予以验证。

Loewner矩阵Moore-Penrose逆的快速算法

给出了求以秩为n的m×n阶Loewner矩阵Moore-Penrose逆的快速算法,该算法的计算复杂度为O(mn)+O(n2)。

Cauchy矩阵Moore-Penrose逆的快速算法

给出了求以秩为n的m×n阶Cauchy矩阵Moore-Penrose逆的快速算法,该算法的计算复杂度为O(mn)+O(n2)。而用C+=(CTC)-1CT求解C+时所需的运算量为O(mn2)+O(n3)

对称Loewner矩阵Moore-Penrose逆的快速算法

对称Loewner矩阵在自然科学及工程技术中有着广泛的应用,许多问题都归结为求对称Loewner矩阵及其相关矩阵的代数问题.论文通过构造特殊分块矩阵并研究其逆矩阵,给出了秩为n的m×n对称Loewner矩阵Moore-Penrose逆的快速算法,该算法的计算复杂度为O(mn)+O(n2),而通过L+=(LTL)-1LT计算的复杂度为O(mn2)+O(n3).实验数据也表明前者在用时和效率方面均优于后者.

计算加权Moore Penrose逆A_(M ,N)^+的一个改进的并行算法(英文)

利用PREPARTAFP和SARWATEDV[6] 的一些结果 ,给出一个计算加权Moore Penrose逆A+MN 的改进的并行算法 ,改善了文献 [8]中提出的算法。在与PREPARTAFP和SARWATEDV文 [6 ]中相同的假设下证明了改进的并行算法的时间复杂性和处理机台数分别为 T =0 ((logn) 2 ) , P =max m/n 2 nα/logn ,2r1 / 2 nα(logrlogn)时空积 (成本最优性 ) T× P小于T×P(T和P分别为 [8]中原有并行算法的时间复杂性和处理机台数 )。

Cauchy型矩阵Moore-Penrose逆的快速算法

给出了求以秩为n的m×nCauchy型矩阵Moore-Penrose逆的快速算法,该算法的计算复杂度为O(mn)+O(n^2).

上双对角阵Moore-Penrose广义逆的并行计算(英文)

研究用一种叫分而治之的算法以计算上双对角阵的Moore-Penrose广义逆.同时给出一个数值例了和一个关于并行效率的定理.

带记忆的Boyer-Moore型模式匹配算法及其复杂性分析

通过构建前缀匹配自动机,使得每轮匹配后下个匹配窗口的文本总是保持左端部分为模式的一个前缀、右端部分全为未比较过的字符的形式.对于与此相应的模式匹配算法,已证明文本内的每个字符在整个匹配过程中最多被比较一次,从而字符总比较次数不超过n,已达到任意算法最坏情况下字符总比较次数的最小值.另外,在适当条件下还从理论上证明了此算法的亚线性(即字符总比较次数小于cn,其中常数c<1).根据实验结果,算法的实际运行速度快于Boyer-Moore算法.

预处理变形共轭梯度法并行求解矩阵的Moore-Penrose逆

提出了一种求解Moore-Penrose逆的并行预处理变形共轭梯度法,将求解Moore-Penrose逆转化求解矩阵方程极小范数解或极小范数最小二乘解的问题.给出了两种预处理方法.一种方法是给出预处理矩阵是可逆对角矩阵,然后并行求解预处理矩阵方程;另一种方法是给出预处理矩阵是严格对角占优矩阵,该方法提出了迭代法的预处理模式,构造并行迭代求解预处理矩阵方程的迭代格式,进而使用变形共轭梯度法并行求解.通过数值试验,这两种预处理方法与直接使用变形共轭梯度法相比较,第二种方法有效提高了收敛速度,而且具有很好的并行性.

Moore-Penrose逆的一个性质特征

对任意的 m× n阶矩阶 A∈Cm× n,给出了 A的 M- P( Moore- Penrose)逆的一个重要性质 ,并由此给出了 A的 M- P中逆的一个求解算法。

加权Moore机的同余与最小化

本文定义了加权Moore机的同余、同态,给出了同态定理并证明了同余关系在加权Moore机中构成一个完备格。在同余关系下给出了加权Moore机的商Moore机,并给出了求最小状态Moore机的算法。

Computing the Moore-Penrose Inverse of a Matrix Through Symmetric Rank-One Updates

This paper presents a recursive procedure to compute the Moore-Penrose inverse of a matrix A. The method is based on the expression for the Moore-Penrose inverse of rank-one modified matrix. The computational complexity of the method is analyzed and a numerical example is included. A variant of the algorithm with lower computational complexity is also proposed. Both algorithms are tested on randomly generated matrices. Numerical performance confirms our theoretic results.

实方阵的Moore-Penrose广义逆的MCG算法探究

证明了矩阵Moore-Penrose逆的唯一性以及建立了求矩阵Moore-Penrose逆的算法。首先将求矩阵的Moore-Penrose逆转为求解含有三个矩阵变量的矩阵方程组,其次建立求该矩阵方程组的修正共轭梯度算法(MCG算法),给出了MCG算法的性质和收敛性证明,对于任意给定的初始矩阵该算法能在有限步迭代计算后得到矩阵的Moore-Penrose逆。最后给出数值算例,证明MCG算法在求解矩阵Moore-Penrose逆中具有很高的计算效率。

实方阵的Moore-Penrose对称{1,3}逆的MCG算法

讨论了广泛运用于控制理论、系统识别等领域的广义逆矩阵问题,借助求线性矩阵方程组的修正共轭梯度算法(MCG算法),提出求方阵对称{1,3}逆的修正共轭梯度算法,并证明了算法的收敛性。数值算例表明,该算法具有很高的计算效率。