不动点问题的异步并行算法

不动点问题的异步并行算法王德人（上海大学，上海应用数学与计算数学研究所）ＡＳＹＮＣＨＲＯＮＯＵＳＰＡＲＡＬＬＥＬＡＬＧＯＲＩＴＨＭＳＯＦＦＩＸＥＤＰＯＩＮＴＰＲＯＢＬＥＭＳ￥ＷａｎｇＤｅｒｅｎ（ＳｈａｎｇｈａｉＵｎｉｖｅｒｓｉｔｙ，ＳｈｏｎｇｈａｉＩ...     

图形分布处理支撑环境DGPSE

本文详细介绍图形分布处理支撑环境ＤＧＰＳＥ的设计和实现技术．ＤＧＰＳＥ有效支持高性能分布式图形应用系统的开发和分布并行图形处理算法的研究．它具有以下特点：支持多种分布处理模型，通讯方式灵活，图形支撑功能强．使用ＤＧＰＳＥ已实现了一分布式图形应用系统和一组分布式图形算法．的设计和实现．南京大学计算机系硕士论文，１９９１．１３潘志庆，石教英．Ｆｒａｃｔａｌ生成的并行算法研究．全国第７届ＣＡＤ和图形学会议论文集，无锡，１９９２．１４石教英，劳志强，潘志庚．多面体扫描转换的分布并行算法．全国第７届ＣＡＤ和图形学会议论文集，无锡，１９９２．     

线性椭圆型方程的一个有限差分异步并行算法

线性椭圆型方程的一个有限差分异步并行算法李磊（西安交通大学数学系）ＡＦＩＮＩＴＥＤＩＦＦＥＲＥＮＣＥＡＳＹＮＣＨＲＯＮＯＵＳＩＴＥＲＡＴＩＶＥＡＬＧＯＲＩＴＨＭＦＯＲＬＩＮＥＡＲＥＬＬＩＰＴＩＣＰＤＥｓ￥ＬｉＬｅｉ（Ｘｉ＇ａｎＪｉａｏｔｏｎｇＵｎｉｖ...     

最小生成树的高效异步并行算法

在ＭＩＭＤ－ＳＭ并行计算模型上，本文给出了时间复杂性为Ｏ（ｎ（ｎ／ｐ＋ｌｏｇｐ））的最小生成树的异步并行算法，其中ｎ，ｐ（１≤ｐ≤ｎ）分别表示图的顶点数和处理机的个数。     

数据库并行处理执行器DB／MA

本文以数据库查询的并行处理为主要线索，从并行求值规划，并行算法，并行处理执行器的结构等建造并行处理建造并行处理执行器的主要技术出发对ＤＢＤ／ＭＡ做了较全面，深入的介绍。     

多处理机上异步并行算法设计(Ⅰ)

本文介绍多处理机上并行算法一些基本问题,同步和异步并行算法基本概念,异步并行算法的正确性和效率分析,并用若干个例子加以分析。     

电脑文摘

０００２３ＦＤＤＩ站管理中间件的实现∥计算机工程与科学．—１９９９（５）．—１３～１７主要探讨了ＷｉｎｄｏｗｓＮＴ环境下ＦＤＤＩ网络适配器驱动程序的实现技术。首先分析了ＮＴ网络驱动程序环境ＮＤＩＳ,然后讨论了ＦＤＤＩ技术即ＳＭＴ站管理中间件的构成,最后阐述了微端口（Ｍｉｎｉｐｏｒｔ）方式实现ＳＭＴ中间件的主要技术。０００２４分布式存储环境下矩阵转置并行算法研究∥计算机工程与科学．—１９９９（５）．—６７～７１针对基于消息传递机制的分布式高性能计算中经常遇到的矩阵转置问题,在分析环状算法的基础上,提出…     

无约束最优化问题的BFGS松弛异步并行算法

为解决大规模非线性最优化问题的串行求解速度慢的问题,提出应用松弛异步并行算法求解无约束最优化问题。根据无约束最优化问题的BFGS串行算法,在PC机群环境下将其并行化。利用CHOLESKY方法分解系数为对称正定矩阵的线性方程组,运用无序松弛异步并行方法求解解向量和Wolfe-Powell非线性搜索步长,并行求解BFGS修正公式,构建BFGS松弛异步并行算法,并对算法的时间复杂性、加速比进行分析。在PC机群的实验结果表明,该算法提高了无约束最优化问题的求解速度且负载均衡,算法具有线性加速比。     

常微分方程初值问题的并行算法

常微分方程初值问题的并行算法刘德贵，宋晓秋（北京计算机应用和仿真技术研究所）ＰＡＲＡＬＬＥＬＡＬＧＯＲＩＴＨＭＳＦＯＲＩＮＩＴＩＡＬＶＡＬＵＥＰＲＯＢＬＥＭＳＦＯＲＯＲＤＩＮＡＲＹＤＩＦＦＥＲＥＮＴＩＡＬＥＱＵＡＴＩＯＮＳ￥ＬｉｕＤｅｇｕｉ；Ｓｏｎｇ...     

多处理机系统上求解非线性方程组的异步并行拟牛顿法

异步并行算法由于在任何时刻它的进程不等待输入,因而异步并行算法与同步并行算法相比效率高得多,但往往算法分析极为困难,本文给出了多处理系统上求解非线性方程组的一种异步并行拟牛顿算法,证明了其收敛性,数值试验例子表明该算法有较好的收敛速度。     

Weighted steepest descent method for solving matrix equations

This paper describes iterative methods for solving the general linear matrix equation including the well-known Lyapunov matrix equation, Sylvester matrix equation and some related matrix equations encountered in control system theory, as special cases. We develop the methods from the optimization point of view in the sense that the iterative algorithms are constructed to solve some optimization problems whose solutions are closely related to the unique solution to the linear matrix equation. Actually, two optimization problems are considered and, therefore, two iterative algorithms are proposed to solve the linear matrix equation. To solve the two optimization problems, the steepest descent method is adopted. By means of the so-called weighted inner product that is defined and studied in this paper, the convergence properties of the algorithms are analysed. It is shown that the algorithms converge at least linearly for arbitrary initial conditions. The proposed approaches are expected to be numerically reliable as only matrix manipulation is required. Numerical examples show the effectiveness of the proposed algorithms.     

Efficient parallel algorithms for path problems in directed graphs

In this paper we describe a technique for finding efficient parallel algorithms for problems on directed graphs that involve checking the existence of certain kinds of paths in the graph. This technique provides efficient algorithms for finding dominators in flow graphs, performing interval and loop analysis on reducible flow graphs, and finding the feedback vertices of a digraph. Each of these algorithms takesO(log² n) time using the same number of processors needed for fast matrix multiplication. All of these bounds are for an EREW PRAM.     

External matrix multiplication and all-pairs shortest path

Algorithms are presented for external matrix multiplication and for all-pairs shortest path computation. In comparison with earlier algorithms, the amount of I/O is reduced by a constant factor. The all-pairs shortest path algorithm even performs fewer internal operations, making the algorithm practically interesting.     

A note on improving the performance of approximation algorithms for radiation therapy

The segment minimization problem consists of representing an integer matrix as the sum of the fewest number of integer matrices each of which have the property that the non-zeroes in each row are consecutive. This has direct applications to an effective form of cancer treatment. Using several insights, we extend previous results to obtain constant-factor improvements in the approximation guarantees. We show that these improvements yield better performance by providing an experimental evaluation of all known approximation algorithms using both synthetic and real-world clinical data. Our algorithms are superior for 76% of instances and we argue for their utility alongside the heuristic approaches used in practice.     

A new fuzzy relational clustering algorithm based on the fuzzy C-means algorithm

In this paper, we show how one can take advantage of the stability and effectiveness of object data clustering algorithms when the data to be clustered are available in the form of mutual numerical relationships between pairs of objects. More precisely, we propose a new fuzzy relational algorithm, based on the popular fuzzy C-means (FCM) algorithm, which does not require any particular restriction on the relation matrix. We describe the application of the algorithm to four real and four synthetic data sets, and show that our algorithm performs better than well-known fuzzy relational clustering algorithms on all these sets.     

Approximation algorithms for minimizing segments in radiation therapy

Intensity modulated radiation therapy (IMRT) is one of the most effective modalities for modern cancer treatment. The key to successful IMRT treatment hinges on the delivery of a two-dimensional discrete radiation intensity matrix using a device called a multileaf collimator (MLC). Mathematically, the delivery of an intensity matrix using an MLC can be viewed as the problem of representing a non-negative integral matrix (i.e., the intensity matrix) by a linear combination of certain special non-negative integral matrices called segments, where each such segment corresponds to one of the allowed states of the MLC. The problem of representing the intensity matrix with the minimum number of segments is known to be NP-complete. In this paper, we present two approximation algorithms for this matrix representation problem. To the best of our knowledge, these are the first algorithms to achieve non-trivial performance guarantees for multi-row intensity matrices.     

网络表示学习算法的分析与验证

网络表示学习算法是社交网络分析领域的一个热点问题。该文旨在研究现有的各种网络表示学习算法,并分析各类算法在不同结构的网络数据中的性能,对3大类别、共10种网络表示学习算法在8个网络上进行了网络节点的多标签分类以验证算法的性能,以此来全面评价各类算法的效果、效率和应用范围。实验结果表明,DeepWalk这种流行的深度学习算法在各种类型的网络中有着稳定而较好的效果。而基于矩阵分解算法的应用,则受限于其较高的空间复杂度。     

Improving on-line construction of two-dimensional suffix trees for square matrices

The two-dimensional (2-D) suffix tree of an n×n square matrix A is a compacted trie that represents all square submatrices of A. We consider constructing 2-D suffix trees on-line, which means, instead of giving the whole matrix A in advance, A is separated and each part of A is given at different time as algorithms proceed. In general, developing an on-line algorithm is more difficult than developing an off-line algorithm. Moreover, the smaller the input grain size is, the harder it is to develop an on-line algorithm. In the case of 2-D suffix tree construction, dealing with a character at a time is harder than dealing with a row or a column at a time.In this paper we propose a randomized linear-time algorithm for constructing 2-D suffix trees on-line. This algorithm is superior to previous algorithms in two ways: (1) This is the first linear-time algorithm for constructing 2-D suffix trees on-line. Although there have been some linear-time algorithms for off-line construction, there were no linear-time algorithms for on-line construction. (2) We deal with the most fine-grain on-line case, i.e., our algorithm can construct a 2-D suffix tree even though only one character of A is given at a time, while previous on-line algorithms require at least a row and/or a column at a time.     

权值矩阵聚类算法

由于以往的算法不能对用户感兴趣的页面进行很好的聚类.所以将网站访问频度作为参数考虑进来,提出一个新的概念--权值关联矩阵,以Web服务器URL为行、以UserID为列建立URL-UserID关联矩阵,与普通的矩阵聚类算法相比,根据用户对某页面的兴趣度,再生成权值关联矩阵.从而发现相似的用户群体和相似的web页面.该算法通过上机实践,与传统的矩阵聚类算法相比具有识别准确率高,用户向量特征描述更准确,且能够更准确的反映网站的访问情况等优点.同时为用户提供个性化推荐服务铺平了道路.     

并行无存储冲突的邻接矩阵算法

邻接矩阵算法在科学计算与信息处理方面有着极为重要的应用,是图论的基础研究之一。针对目前邻接矩阵算法多是基于串行,或并行SIMD模型而无法解决存储冲突的问题,提出一种基于SIMD-EREW共享存储模型的并行邻接矩阵算法。算法使用O(p)个并行处理单元,在O(n2/p)的时间内完成对n个数据点邻接矩阵的计算。将提出算法与现有算法进行的性能对比分析表明:本算法明显改进了现有文献的研究结果,是一种并行无存储冲突的邻接矩阵算法。