一类递推方程的一个新的优化向量并行算法

本文提出一种新的解Ｋｏｇｇｅ和Ｓｔｏｎｅ所定义的一类递推方程的优化的并行算法，当采用ｐ台处理机，对规模为Ｎ的一类递推方程求解时，该算法的加速比为Ｏ（ｐ），其中１≤ｐ≤Ｎ＾１－ε，ε是一个任意小的正数，与已有的并行算法相比，该算法具有效率高，适用范围广的优点，该算法可以在ＥＲＥＷ ＰＲＡＭ模型机上实现，也可以在具有素数内存系统的流水线向量处理机上实现。     

近似三对角Toeplitz方程组的快速分布式并行算法

利用近似三对角Toeplitz矩阵的特殊结构,提出了一种新的求解近似三对角Toeplitz方程组的快速算法．在三对角Toeplitz矩阵的近似LU分解的基础上,利用“分而治之”的思想,并结合秦九韶技术和特殊的数学技巧减少大量的冗余计算,提出了求解近似Toeplitz三对角方程组的快速分布式并行算法,并在理论上证明了算法具有近似于线性的加速比．最后通过数值实验证明,新的并行算法具有较高的并行效率,并且当矩阵阶数n足够大时,算法的加速比趋近于线性加速比．     

求解模糊线性方程组的并行分割算法

在简化方法的基础上，提出了在MIMD模型上采用异步通信模式求解模糊线性方程组的分布式并行分割算法，算法有效地平衡了负载，并分析了算法的时间复杂性和通信复杂性。     

块三对角线性方程组的一种分布式并行算法

提出了分布环境下求解三对角线性方程组的一种并行算法,该算法基于对计算量的仔细估算,合理地将方程组求解工作分配到各处理机,达到负载平衡,同时,充分地将计算与通信重叠,减少处理机空闲时间;当块三以角线性方程组的系数矩阵为对角占优时,算法在执行过程中不会中断;文中分析了算法的复杂性,给出了在分析布存储多计算机系统上的数值试验结果,数值结果表明,文中算法的效率较Ｃｈｕｎｇ等的算法有较大的提高。     

Explicit Solution for a Class of Discrete‐Time Algebraic Riccati Equations

In the present paper we obtain an explicit closed‐form solution for the discrete‐time algebraic Riccati equation (DTARE) with vanishing state weight, whenever the unstable eigenvalues are distinct. We discuss links to current algorithmic solutions and observe that the AREs in such a class solve on one hand the infimal signal‐to‐noise ratio (SNR) problem, whilst on the other hand, in their dual form they solve a Kalman filter problem. We then extend the main result to an example case of the optimal linear quadratic regulator gain. We relax some of the assumptions behind the main result and conclude with possible future directions for the present work.     

Parallel Processing of First Order Linear Recurrence on SMP Machines

In this paper, we propose a new algorithm that analyzes the data dependency pattern in the first-order linear recurrence (FOLR) and transforms it into algebraically equivalent expanded form so that it can be processed in parallel using the threads on symmetric multiprocessor (SMP) machines. The transformation aims to eliminate the data dependencies in the naive nested form of the FOLR. However, as this transformation may result in extra multiplication operations, our algorithm examines the immanent overhead of the expanded form of the FOLR and generates a new hybrid form of the FOLR. The hybrid form combines nested and appropriately expanded form in order to make it suitable for parallel processing. The parallel algorithm based on the hybrid form of the FOLR is analytically examined and tested through implementation on SMP machines. The implementation details, such as the workload balancing between processors and the optimization of cache performance, are also discussed. The experimental results show that the parallel algorithm based on the hybrid form of the FOLR considerably improves the performance on SMP machines that have three of more processors.     

块带状线性方程组的分布式并行算法

本文首先根据分而治之的思想提出一种新的求解块三地角线性方程组的分布式并行算法,然后将该算法推广到块五对角线性方程组和块七地角线方程组的并行求解,并对算法进行了性能分析。 ＳＧＩ工作站机群和５８６微机群上试算表明,加速比呈线性增加。     

周期时变线性系统的一般线性二次型最优控制

讨论周期时变线性系统的一般线性二次型最优控制问题, 即状态方程为非齐次方程且二次型性能指标包含线性项的一般情况. 给出了该问题可解的一系列充分必要条件, 同时给出了最优控制的解析构造以及最优性能指标值.     

A Parallel Logarithmic Order Algorithm for General Multibody System Dynamics

A novel optimal order optimal resource parallel multibody algorithm with general system applicability is derived directly from the sequential recursive methods and the most recent developments in recursive constraint treatments. This new Recursive Coordinate Reduction Parallelism (RCRP) is the first optimal order parallel direct method with a sequential implementation that is exactly the efficient algorithm. Consequently, the RCRP sets new benchmarks for performance over a wide range of problem size and parallel resources. Comparisons to existing methods also demonstrate that the RCRP is presently the best general parallel method.     

基于递归耦合方法的三对角线性方程组分布式并行算法

提出了一种在分布式计算机上用递归倍增方法解三对角线性方程组的并行算法。通过研究算法中的额外开销达到优化标量算法的执行和通讯,并减少了存储开销。当三对角线性方程组的系数矩阵满足对角占优时,该算法在运行过程中不会中断。最后,在采用消息传递编程模型的基于局域网MPI并行环境下对算法进行了评价。数值实验结果表明,该算法是高效的。     

K-Dimensional Optimal Parallel Algorithm for the Solution of a General Class of Recurrence Equations

This paper proposes a parallel algorithm,called KDOP (K-Dimensional Optimal Parallel algorithm),to solve a general class of recurrence equations efficiently.The KDOP algorithm partitions the computation into a series of subcomputations,each of which is executed in the fashion that all the processors work simultaneously with each one executing an optimal sequential algorithm to solve a subcomputation task.The algorithm solves the equations in O(N/P) steps in EREW PRAM model (Exclusive Read Exclusive Write Parallel Random Access Machine model) using p≤N^1-∈ processors,where N is the size of the problem,and ∈ is a given constant.This is an optimal algorithm (its sepeedup is O(p)) in the case of p≤N^1-∈.Such an optimal speedup for this problem was previously achieved only in the case of p≤N^0.5.The algorithm can be implemented on machines with multiple processing elements or pipelined vector machines with parallel memory systems.     

并行J-变量块Cholesky分解算法的仿真研究

该文提出一个针对大型实对称正定稠密方程组或复对称非Hermitian稠密方程组线性求解器的并行分布式算法。它使用了不同于ScaLAPACK的J-变量块Cholesky分解算法和一维块循环列数据分配。该算法以MPI作为消息传递库,在最多可达16个处理器的集群上针对实对称正定稠密方程组可提供与ScaLAPACK近似的浮点操作性能,并可解决一些涉及复对称非Hermitian稠密方程组的电磁场散射问题。该算法的优点是执行Cholesky分解所需的存储量只是标准并行库ScaLAPACK的一半。仿真的数值结果表明该算法是正确、有效的。     

Optimal Parallel Algorithm for the Knapsack Problem Without Memory Conflicts

Abstract The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is adopted. The proposed algorithm is based on an EREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past researches.     

大型线性方程组求解的可验证外包算法

随着云计算的发展,可验证的外包计算受到了越来越多的关注。对普通用户来说,大型线性方程组的求解是一个困难问题,可通过外包计算进行解决。现有的大型线性方程组外包求解方案计算效率较低或计算结果无法完全验证。本文提出了一个可验证的大型线性方程组求解的外包计算协议。在完全保护用户隐私的前提下,所提方案大大提高了用户的计算效率。与同类方案相比,所提方案降低了用户的计算代价,且用户可以完全验证服务器的外包计算结果。     

求广义指派决策问题最优解的有效算法

分析和研究一类广义指派决策问题,给出了该问题的线性规划模型,并把该问题转化为传统指派决策问题,使得该问题可以用著名的匈牙利算法求解最优解,从而为该问题找到一个理想,简便而有效的求解方法,给出了一个数值例子。     

Communication Optimization for Affine Recurrence Equations Using Broadcast and Locality

This paper deals with communication optimization which is a crucial issue in automatic parallelization. From a system of parameterized affine recurrence equations we propose a heuristic that determines a set of efficient space-time transformations. It focuses on distant communications removal using broadcast—including anticipated broadcast, and locality enforcement.     

Parallel Wavefront Algorithms Solving Lyapunov Equations for the Cholesky Factor on Message Passing Multiprocessors

In this paper new parallel algorithms to solve the Lyapunov equations for the Cholesky factor using Hammarling's method on message passing multiprocessors are described. These algorithms are based on previous work carried out on the parallel solution of triangular linear systems by using row block data distribution and a wavefront of antidiagonals. The algorithms are theoretically analyzed and experimental results obtained on an SGI Power Challenge and a Cray T3D are presented.     

求解线性与非线性方程组的单调异步迭代并行算法

针对偏序情形，构造一类适用于多处理机系统的求解线性与非线性方程组的异步迭代并行算法，并对其单调收敛性条件进行了严格的理论分析。此外，还用数值试验证实了这些结果。     

解大规模线性方程组的Mann迭代并行算法

利用实函数不动点的Mann迭代算法,提出了一种求解大规模线性方程组新的并行算法,分析了算法的并行加速比,讨论了算法在基于消息传递机制的MPI并行环境下的实现流程,给出了并行环境上的实验.该算法适用范围广,数值计算结果表明理论分析与实际计算相符合,算法在并行环境下具有较好的并行度,可适合大规模科学与工程的高性能计算.     

A Parallel Algorithm for determining the inverse of a matrix for use in blockcipher encryption/decryption

In the current world that we live in, of rapid growing technology, and especially reliance on the Internet for our daily lively hood (Banking, shopping, entertainment, news), and also with current crimes (Identity-theft, hacking, spyware), computer security is becoming more and more important. By “computer security” we often refer to addressing three important aspects of a computer-related system: Confidentiality, integrity, and availability. Encryption clearly addresses the need for confidentiality of data, both in storage and transmission. However, the use of encryption can be cumbersome and time consuming. It is important to have a fast algorithm to both encrypt and decrypt data as needed. Public key encryption, though secure, is definitely not fast enough to be used for large size data. We introduce a Parallel Algorithm for computation of inverses of matrices modulo n. This is used in conjunction with Block Ciphers and Hill Ciphers in symmetric encryption and decryption of data for transmission on open lines. Experimental studies were done to compare the run-time of this algorithm on parallel machines, to the traditional one. The new algorithm was found to perform much better than the traditional one, and would be useful to use in encryption/decryption of large sensitive data.