mn阶分块(R,r)-循环矩阵相乘和特征值计算的快速算法

本文利用快速富里叶变换（FFT），给出了mn阶分块（R，r)－循环矩阵相乘和特征值计算的快速算法，其时间复杂性均为O（mnlog2mn）。     

r—循环分块矩阵求逆和线性方程组的快速算法

1引言与引理阵．因此,对它的研究就引起了人们的高度重视［‘－’］．近年来,特别是对（块）循环矩阵的有关快速算法更为重视．由于（块）循环矩阵与离散傅里叶变换之间的关系,到目前为止几乎所有与（块）循环矩阵的有关快速算法都建立在傅里叶交换之上,而实际问题中的数据大多为实数,因此用FFT快速求（块）循环矩阵的有关问题时需将实数转化为复数运算而影响效率,如卜9］．本文利用多项式矩阵理论给出一般。循环分块矩阵有关的一种快速算法,它拓广和改进了［7－－9］的结果;另外,该快速算法也容易在计算机上实现且存贮量少,只…     

关于(R,r)-循环分块矩阵求逆与相乘的一种快速算法

利用矩阵分块逐次降阶的方法和快速富里叶变换(FFT),给出了mn阶(R,r)-循环分块矩阵求逆与相乘的一种快速算法,证明了其计算复杂性为O(mnlog2mn).     

以仅有两个互异正特征值的单构矩阵为系数的一类单块法

1．引言众所周知，解刚性常微分方程组初值问题的单块法具有良好的并行性，这里，是Kronecker乘符，为单位矩阵，Yn构造出多种A一稳定或L一稳定的r点r阶，r＋1阶，甚至r＋2阶的单块法［1－5］．但一般而言，当用Newton（型）法解（1．幻时，需对形如的矩阵做多次LU分解，当mr较大时，计算量相当巨大．为克服这一缺点，许多作者进行了努力［‘，‘，＼特别是［6］中提出的。点r阶A一稳定或L一稳定的经济隐式单块法（EIBM）X＋1＝X＋h（BO兄＊q凡十1），q21／2，（1．4）当精度要求不太高，且右函数f的计值工作量与m阶矩阵的LU分解工…     

关于一种循环类预条件方程组的快速求解

１引言考虑下列Ｎ阶线性方程组其中Ｃ１＝,Ｃ２＝０≤ｉ,ｊ≤Ｎ－１,是Ｎ阶循环矩阵,Ｊ１＝（Ｊ）是Ｎ阶置换矩阵,其元素分别满足１９９３年,Ｔ,Ｋ．Ｋｕ,Ｃ．Ｃ．Ｊ．Ｋｕｏ在［１］中取Ｃ１,Ｃ２为实对称循环矩阵,而Ｃ１＋Ｊ１Ｃ２作为预条件矩阵来求解在数字信号处理中有一定应用的Ｔｏｅｐｌｉｔｚ加Ｈａｎｋｅｌ线性方程组［２］,得到了一种高效的预处理其轭梯度算法．当Ｔｏｅｅｌｉｔｚ与Ｈａｎｋｅｌ矩阵之和为正定矩阵且条件数适中时,所需运算量可达到０（Ｎｌｏｇ２Ｎ）,比原有算法［２,３,４］的运算量０（Ｎ２）…     

异步并行非线性对称Gauss-Seidel迭代算法

1．引言考虑非线性方程组其中A＝（a。。）EL（＊”）为＊一矩阵，B＝（衬。）EL（＊”）为非负矩阵，呐X）一（p。（X。》，4（二）＝（吵k（kk》：＊一＊一为连续的对角映射，而6＝（6k）E＊一为已知向量．这里，什小：”一”均可微，但二者的导函数并不一定连续．这类方程组具有丰富的实际背景．例如，描述冰体溶解过程的著名的Stefan问题，就可归结为问题（1·1）的数值求解（见［l］）．为在多处理机系统上有效地求解问题（1．1），文山利用这类非线性方程组的特殊结构，建立了一类并行非线性Gauss—Seidel型迭代算法．为避免该算…     

对称Toeplitz系统的快速W变换基预条件子

１．引言考虑下列Ｎ阶线性方程组其中T_N=(t_i,j)　是Ｎ×Ｎ阶实对称正定（ＳＰＤ）Ｔｏｅｐｌｉｔｚ矩阵,即０,１,…,Ｎ－１）且Ｔ_Ｎ的所有特征值为正数．Ｔｏｅｐｌｉｔｚ系统已广泛应用于数字信号处理,时间序列分析（参见［１］）以及微分方程的数值解（参见［２１］等领域．八十年代以前,考虑到Ｔｏｅｐｌｉｔｚ矩阵的特殊性,人们主要用Ｌｅｖｉｎｓｏｎ递推技术及其变形或者分而治之思想直接求解方程组（１．１）,计算复杂性为Ｏ（Ｎ~（２））或Ｏ（ＮｌｏｇＮ~（２））（参见［３］）;比Ｇａｕｓｓ法运算量级Ｏ（Ｎ~（３）…     

关于具优势对称部分的不定线性代数方程组的分裂极小残量算法

１．引 言 考虑大型稀疏线性代数方程组 为利用系数矩阵的稀疏结构以尽可能减少存储空间和计算开销，Ｋｒｙｌｏｖ子空间迭代算法［１，１６，２３］及其预处理变型［６，８，１３，１８，１９］通常是求解（１）的有效而实用的方法．当系数矩阵对称正定时，共轭梯度法（ＣＧ（     

线性流形上矩阵方程AX=B的一类反问题及数值解法

1．引言本文用＊-"m表示全体nX。实矩阵的集合，人表示n阶单位矩阵，汉"m一《ME＊""叫rank（川一r），＊＊"""＝HE＊"""卜"A＝v，＊＊"""一仰E＊"""卜"一M｝，SR；""（SR7""）表示全体7。阶实对称半正定（正定）阵集合．N（A）表示矩阵A的零空间，即N（A）＝（xlAx＝0），ID叫D表示Frobenius范数，A"表示矩阵A的Moors－Penrose广义逆，［EI十表示在Frobenius范数意义下n阶方阵E在SR；""中唯一的最佳k逼近解，即口一［E］＋11-inf。。、。。x，IllE-All．（［E］十求法见文［7］）．还用A三0（A三0）表示A（的k阶顺序主子矩…     

大型稀疏线性互补问题的行作用法

且引言考虑线性互补问题＊＊P（q，M）：求X二（X；，x。，…，x。厂E”使得x＞O，训x）E＊x＋g＞o，／U（X）一O（1）其中M一（m；。）为nXn矩阵（不必对称），q一切，q。，…，q。）rER“为给定常向量．通常情况下已有求解LCP（q，M）的若干著名算法［‘－’j．本文提出求解LCP（q，M）的一种新算法一行作用法，方法具有如下特点：（i）每次迭代只需n个简单的投影运算，每次投影只涉及矩阵M的一行；（n）生成新的迭代点x‘“‘时只利用前次迭代点／；（iii）对矩阵M不实施任何整体运算．因而适合于求解大型（巨型）稀疏问题，且…     

一维双曲守恒方程组的Taylor-Galerkin有限元方法

１．引言 在文章［８］中,利用双曲守恒律的Ｈａｍｉｌｔｏｎ－Ｊａｃｏｂｉ方程形式,应用 Ｇａｌｅｒｋｉｎ有限元给出了求解一维双曲守恒律的计算方法．不同于间断有限元方法［２］、［３］和 Ｔａｙｌｏｒ－Ｇａｌｅｒｋｉｎ有限元方法［１］求解双曲守恒律,文章［８］采用连续 Ｇａｌｅｒｋｉｎ有限元求解双曲守恒律． 在文章［８］中,对差分方法和有限元方法求解双曲守恒律作了较为详细的讨论．同时在文章［８］中,采用积分变换,将双曲守恒律方程变成 Ｈａｍｉｌｔｏｎ－Ｊａｃｏｂｉ方程形式．由于 Ｈａｍｉｌｔｏｎ－Ｊａｃｏ…     

对凝聚函数法的探讨

1．引言考虑问题（）：这里人（n）是”中二次连续可微函数，n，n是正整数．（利是非光滑规划中常见的一种情形，且光滑约束优化问题的某种罚函数也是这种形式．因此如何有效地求解（P）是非线性规划中一个重要的课题［’‘］．凝聚函数法是近几年发展起来的一种重要的求解（P）的方法［“‘l，其想法比较简单：用一族二次连续可微的凝聚函数Fp（x）去一致逼近f（x）（PM＋co），从而当p充分大时，用几（X）的极小解X（叫作为（日的近似解．因为马（X）是＊”中光滑函数，所以可用己知的求解光滑无约束优化的数值方法（如＊＊＊S方法）…     

一个求解单调线性互补问题的高阶不可行内点算法

本文通过使用相同的矩阵因子，给出了一个求解单调线性互补问题的r-阶Mehrotra型宽城不可行内点算法，其中嵌入Wright的快速步与安全步算法．所给算法的迭代复杂性为O（n~((r 1)/r)L）．在考虑的问题有一个严格互补解的条件下，所给算法具有2阶Q-超线性收敛性．     

广义块Broyden方法与超定方程组求解

1．引言［1］提出用块Broyden方法求解成组的线性与非线性方程组，同时证明了：若有p组n阶线性方程组则块Brorden方法具有至多2n／p步的有限终止性．这种块形式算法，对于大型成组问题的计算，在计算量和存储量方面，都会有相当的改善，并且有利于并行计算．本文推广上述结果，建立一种广义块nroxaen方法，并将它应用于成组的超定方程组的求解．我们证明了对于给出的p组。x叫x三叫的线性超定方程组其中AeRm””，x；e＊”，kEBm，广义块Broxden方法同样具有至多z。／r步的有限终止性，这表明超定方程组的纽数越多（P5…，方法所需的选代…     

按环路α-连对角占优阵及应用

１．引言与记号 利用矩阵的对角占优性研究矩阵的特征值分布和非奇Ｈ矩阵的判定,是数值代数的重要课题．［１］－［４］给出了利用 Ｏｓｔｒｏｗｓｋｉ定理及连对角占优性判定非奇 Ｈ－矩阵的最新成果．本文引入按环路α－连对角占优概念,给出了非奇Ｈ－矩阵的判定条件及等价表征,简化了计算,改进与推广了［１］－［９］的相应结果． 设Ａ＝．Γ（Ａ）表 Ａ的方向图,其顶点集及弧集分别记作 Ｖ（Ａ）及 Ｅ（Ａ）,ｅｉｊ表从顶点ｉ到顶点 ｊ的弧, Ｃ（Ａ）表 Γ（Ａ）中非平凡环路集合．对任意固定 α Ｅ［０,１］还记＊ｋ伪行、列足…     

DAE的Runge-Kutta方法在不可压NS方程求解中的应用

1．引言自然界中的流场通常是非定常复杂流场，要正确模拟和跟踪复杂流场的变化，计算格式的时间精度极为重要．对于常微分方程（＊＊q，一般采用＊K方法及线性多步法来提高格式的时间精度．前者是单步法，在计算过程中可以改变步长，可找到稳定性较好的高精度格式：近年来在发展到偏微分方程的数倩水解中也有很多应用．原始变量的INS方程（二维）为：其中u，v分别是x，y方向速度分量，r是压力，连续方程（1．幻可视为约束条件．从［1］，［2］可见，经空间差分化后（固定空间网格），它可看作带约束的微分方程组，即微分代数方程（DAE－…     

分块K—循环Toeplitz矩阵求逆的快速付氏变换法

1算法描述及推导 Toeplitz矩阵及Toeplitz系统的求解在谱分析、线性预测、误差控制码、自回归滤波器设计等领域内起着重要的作用~[1-3]，而分块Toeplitz矩阵在计算机的时序分析、自回归时序模型滤波中也经常出现~[4]。对一般Toeplitz矩阵求逆，其算术复杂性为O(n~2)~[5]-[6]，其中n为Toepleitz矩阵的阶，而K-循环Toeplitz矩阵的求逆，其算术复杂性可降为O(nlog_2n)，本文提供了mn附分块K-循环Toeplitz矩阵求逆的一种快速付氏变换算法，其算术复杂性为O（mnlog_2mn）.     

求解一类非单调线性互补问题的路径跟踪法及其计算复杂性

１．引言及记号 线性互补问题的一般形式是;求（ｘ,ｓ） 　　　　　　　 使其中 众所周知,当Ω＋非空时,单调线性互补问题可在多项式时间内求解,而且人们已经设计出了多种求解单调线性互补问题的有效的内点算法（见［１］和［７］）．然而,对于求解非单调线性互补问题的内点算法的研究可以说才刚刚开始．文［２］讨论了当Ｍ为Ｐ矩阵时问题（１）的中心路径的存在唯一性;文［３］给出了设计求解一类非单调线性互补问题的内点算法的一般框架;文［４］给出了求解一类非单调线性互补问题的一种势能函数约减法并讨论了其算法的计算复杂…     

（r）循环矩阵的Kronecker积

（ｒ）循环矩阵的Ｋｒｏｎｅｃｋｅｒ积韩瑞珠（东南大学）循环矩阵是一类很重要的矩阵，它有着广泛的应用［１］，并且有许多独特的性质。例如，循环阵的广义道［１］、逆矩阵［２］、伴随阵［３］仍为循环阵；循环阵的乘积仍为循环阵。自然地，作为矩阵论中有极其重要的...     

解非对称矩阵特征值问题的一种并行分治算法

１引言考虑矩阵特征值问题其中Ａ是非对称矩阵．通过正交变换（如Ｈｏｕｓｅｈｏｌｄｅｒ变换或Ｇｉｖｅｎｓ变换）,Ａ可化为上Ｈｅｓｓｅｎｂｅｒｇ形．因而,本文假设Ａ为上Ｈｅｓｓｅｎｂｅｒｇ矩阵,表示如下：不失一般性,进一步假设所有的（ｊ＝２,…,ｎ）,即认为Ａ是不可约的关于如何求解上述问题,人们进行了不懈的努力,提出了许多行之有效的算法［１－８］．其中分治算法因具有良好的并行性而引人注目．分治算法的典型代表是基于同伦连续的分治算法［２,３,４］和基于Ｎｅｗｔｏｎ迭代的分治算法［１］．本文提出一种新的分…