反对称矩阵的一种计算方法

本文讨论反对称矩阵的数值计算问题．指出联立方程求解可以用分块矩阵ＬＤＬ^Ｔ算法．对于反对称阵的辛本征问题论述了辛雅可比算法，辛Ｈｏｕｓｅｈｏｌｄｅｒ变换．分块三对角化等．对最优控制、结构力学、波的传播等，是一种好的算法．     

椭圆边值问题的概率算法

本文重新建立了椭圆边值问题的概率模型,在Ｍｏｎｔｅ－Ｃａｒｌｏ算法的基础上,引入了一种新的高精度概率算法,取得很大进展．     

Drazin逆的一个性质特征

对任意的ｎ阶方阵A ∈C^n×n，本文给出它的Ｄｒａｚｉｎ逆的一个重要性质（见定理１），并给出Ａ的Ｄ－逆的一个求解算法，从而推广了［２］中的结论．     

最优消除顺序的B＆B算法

讨论了最优节点消除顺序的性质，并给出了计算最优消除顺序的Ｂ＆Ｂ算法．     

褶积模型参数的估计及模拟试验

在褶积模型中关于混合相位子波反演问题一直受到人们的广泛的关注,这类模型在地震记录反演过程中起着特别重要的作用．该文在引入介入子波的概念的基础上拟订了一套算法将统计递归算法与以高阶标准累积矩作为判据的迭代算法结合起来,最终获得的不是反子波的估计,而是混合相位子波的估计．模拟试验表明该文所拟订的算法对混合相位子波(其反子波具有有限长度)的估计是有效的．     

基于方向信息测度的图像边缘检测

边缘检测是图像处理中—个重要的研究课题．针对传统图像边缘检测算法对噪声敏感的问题,本文在分析图像像素灰度信息的基础上,建立了—个改进的确定方向信息测度的方法,并利用震动滤波对边缘检测图像进行增强,该方法在滤除噪声的同时,能有效地保留图像的基本目标信息,正确提取图像的边缘．     

关于Fuzzy度量点式刻画的一点注记

本文中重新定义由一个点式Ｆｕｚｚｙｐ．ｑ．度量ｄ所诱导的Ｆｕｚｚｙｐ．ｑ．度量｛Ｄｒ｜ｒ＞０｝（代替［１］中的相关重域映射族）．在新的定义下，点式Ｆｕｚｚｙｐ．ｑ．（ｐ．）度量与Ｆｕｚｚｙｐ．ｐ．（ｐ．）度量之间有令人满意的──对应关系．     

非负张量分解的不平衡乘性更新

针对非负张量分解的乘性更新算法,讨论了其元素形式与矩阵形式的一致性,并给出了不平衡的乘性更新算法．数值试验表明,新的算法具有更快的收敛性．     

对格上Erceg式p．q．（p．）度量的注记

本文的主要结果是大幅度地简化了Ｅｒｃｅｇ引入的不分明度量的无点化定义，建立了相应的点式刻画．     

A Theorem for Generalized Extension ofOperators and Some Applications

In this note it is shown that every bounded linear operator T Э B(Y,Z)defined on a closed subspace Y of a Banach space X admits a generalized extension T Э B(X, V). Some examples of the applications are given; especially, a characterization of H.I. spaces is obtained.     

An efficient and numerically correct algorithm for the 2D convex hull problem

An efficient and numerically correct program called FastHull for computing the convex hulls of finite point sets in the plane is presented. It is based on the Akl-Toussaint algorithm and the MergeHull algorithm. Numerical correctness of the FastHull procedure is ensured by using special routines for interval arithmetic and multiple precision arithmetic. The FastHull algorithm guaranteesO(N logN) running time in the worst case and has linear time performance for many kinds of input patterns. It appears that the FastHull algorithm runs faster than any currently known 2D convex hull algorithm for many input point patterns.     

A note on parallel depth first search

The subject of this note is the parallel algorithm for depth first searching of a directed acyclic graph by Ghosh and Bhattacharjee. It is pointed out that their algorithm does not always work. A counter example is given. This paper also states the necessary and sufficient condition for the algorithm to fail, or to work correctly.     

文献优选统计模型及其应用

本文给出了一个复完全有向图顶点排序标法，并利用该算法建立了具有实际应用价值的文献优选统计模型。     

Nonlinear Smoothing and the EM Algorithm for Positive Integral Equations of the First Kind

We study a modification of the EMS algorithm in which each step of the EMS algorithm is preceded by a nonlinear smoothing step of the form , where S is the smoothing operator of the EMS algorithm. In the context of positive integral equations (à la positron emission tomography) the resulting algorithm is related to a convex minimization problem which always admits a unique smooth solution, in contrast to the unmodified maximum likelihood setup. The new algorithm has slightly stronger monotonicity properties than the original EM algorithm. This suggests that the modified EMS algorithm is actually an EM algorithm for the modified problem. The existence of a smooth solution to the modified maximum likelihood problem and the monotonicity together imply the strong convergence of the new algorithm. We also present some simulation results for the integral equation of stereology, which suggests that the new algorithm behaves roughly like the EMS algorithm. Accepted 1 April 1997     

Minimal perfect hashing in polynomial time

We present a universally applicable algorithm for generating minimal perfect hashing functions. The method has (worst case) polynomial time complexity in units of bit operations. An adjunct algorithm for reducing parameter magnitudes in the generated hash functions is given. This probabilistic method makes hash function parameter magnitudes independent of argument (input key) magnitudes.     

An optimal time algorithm for finding a maximum weight independent set in a tree

The maximum weight independent set problem for a general graph is NP-hard. But for some special classes of graphs, polynomial time algorithms do exist for solving it. Based on the divide-and-conquer strategy, Pawagi has presented anO(|V|log|V|) time algorithm for solving this problem on a tree. In this paper, we propose anO(|V|) time algorithm to improve Pawagi's result. The proposed algorithm is based on the dynamic programming strategy and is time optimal within a constant factor.     

A systolic generation of combinations

A parallel algorithm for generating all combinations ofm (m fixed) items out of anyn given items in lexicographic order is presented. The computational model is a linear systolic array consisting ofm identical processing elements. This algorithm requires {ie23-1} time-steps for the {ie23-2} combinations, that is, one output at each time-step. Since all processing elements perform the same program, it is suitable for VLSI implementation. Based on mathematical induction, such an algorithm is proved to be correct.     

Formal neighbourhoods, combinatory Böhm trees, and untyped normalization by evaluation

We prove the correctness of an algorithm for normalizing untyped combinator terms by evaluation. The algorithm is written in the functional programming language Haskell, and we prove that it lazily computes the combinatory Böhm tree of the term. The notion of combinatory Böhm tree is analogous to the usual notion of Böhm tree for the untyped lambda calculus. It is defined operationally by repeated head reduction of terms to head normal forms. We use formal neighbourhoods to characterize finite, partial information about data, and define a Böhm tree as a filter of such formal neighbourhoods. We also define formal topology style denotational semantics of a fragment of Haskell following Martin-Löf, and let each closed program denote a filter of formal neighbourhoods. We prove that the denotation of the output of our algorithm is the Böhm tree of the input term. The key construction in the proof is a “glueing” relation between terms and semantic neighbourhoods which is defined by induction on the latter. This relation is related to the glueing relation which was earlier used for proving the correctness of normalization by evaluation algorithm for typed combinatory logic.     

A note on optimal multiway split trees

Split trees are suitable data structures for storing records with different access frequencies. Under assumption that the access frequencies are all distinct, Huang has proposed anO(n ⁴ logm) time algorithm to construct an (m+1)-way split tree for a set ofn keys. In this paper, we generalize Huang's algorithm to deal with the case of non-distinct access frequencies. The technique used in the generalized algorithm is a generalization of Hesteret al.'s, where the binary case was considered. The generalized algorithm runs inO(n ⁵ logm) time.     

Left distance binary tree representations

We present a new scheme for representing binary trees. The scheme is based on rotations as a previous scheme of Zerling. In our method the items of a representation have a natural geometric interpretation, and the algorithms related to the method are simple. We give an algorithm for enumerating all the representations for trees onn nodes, and an algorithm for building the tree corresponding to a given representation.This work was supported by the Academy of Finland.