Regular Model Checking using Widening Techniques

In this paper, we consider symbolic model checking of safety properties of linear parametrized systems. Sets of configurations are represented by regular languages and actions by regular relations. Since the verification problem amounts to the computation of the reachability set, we focus on the computation of R^*(φ) for a regular relation R and a regular language φ. We present a technique called regular widening that allows, when it terminates, the computation of either the reachability set R^*(φ) of a system or the transitive closure R^* of a regular relation. We show that our method can be uniformly applied to several parametrized systems. Furthermore, we show that it is powerful enough to simulate some existing methods that compute either R^* or R^*(φ) for each R (resp. φ) belonging to a subclass of regular relations (resp. belonging to a subclass of regular languages).     

Parallel nested dissection

Nested dissection is a very popular direct method for solving sparse linear systems that arise from finite difference and finite element methods. Worley and Schreiber [16] give a fine grain algorithm for a square array of processors. Their algorithm uses O(N²) processors, each with O(N) memory, to factor an N² by N² sparse matrix whose graphs is an N × N mesh. The efficiency of their method is between 1/46 and 1/12. George et al. [6] [8] give a medium grain algorithm for hypercube architecture, while George et al. [7] give an algorithm for shared memory machines. These papers present a column oriented approach which can exploit O(N) parallelism and yield efficiencies up to 50%. Lucas [11] also gives a column oriented scheme which achieves up to 75% efficiency and O(N) parallelism. In this paper, we present a medium to fine grain algorithm for a P × P array of processors with local memory. This algorithm can exploit up to O(N²) parallelism. The efficiency of the fine grain version is comparable to [16] while as a medium grain algorithm achieves about 49% efficiency. The strength of the method is due to three factors: its ability to pipeline much of the computation, overlapping computation and communication, and the use of level 3 BLAS like primitives. In addition to its high efficiency its memory requirement is optimal, only O(N² log N/P²) words memory is needed per processor.     

Efficient algorithms for computing two nearest-neighbor problems on a rap

This paper makes an improvement of computing two nearest-neighbor problems of images on a reconfigurable array of processors (RAP) by increasing the bus width between processors. Based on a base-n system, a constant time algorithm is first presented for computing the maximum/minimum of N log N-bit unsigned integers on a RAP using N processors each with N^1/c-bit bus width, where c is a constant and c ≥ 1. Then, two basic operations such as image component labeling and border following are also derived from it. Finally, these algorithms are used to design two constant time algorithms for the nearest neighbor black pixel and the nearest neighbor component problems on an N^1/2 × N^1/2 image using N^1/2 × N^1/2 processors each with N^1/c-bit bus width, where c is a constant and c ≥ 1. Another contribution of this paper is that the execution time of the proposed algorithms is tunable by the bus width.     

On the global linearization of bilinear systems

The problem of finding a global state space transformation to transform a given single-input homogeneous bilinear system to a controllable linear system on Rⁿ is considered here. We show that the existence of a solution of the above problem is equivalent to the existence of a local state space transformation that carries the corresponding bilinear system locally to a controllable linear one. The complete analysis of the globally state linearizable bilinear systems in R² and R³ is also included.     

Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E), Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where ¦V¦= n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B < V, and it requires O(n²(n − n_A − n_b)R_AB) time in this case, where n_a = ¦A¦, n_B = ¦B¦ and r_AB is the number of all minimal A−B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_σ is the number of all minimal separators of G and R_ΣR⁺_Σ = ∑_1i, v_j) ER_vivj n − 1)/2 − m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ+n log nR_Σ) on a CREW PRAM with O(n³) processors.     

Parallel marching Poisson solvers

The paper presents parallel algorithms for solving Poisson equation at N² mesh points. The methods based on marching techniques are structured for efficient parallel realization. Using orthogonal decomposition properties of arising matrices, the algorithms can be formulated in terms of transformed vectors. On a MIMD computer with not more than N processors, the computations can be performed in horizontal slices with minimal synchronization requirements. Considering an SIMD machine with N² processors, the complexity bound O(log N) has been achieved, whereby the single marching requires 10 log N steps only.     

An optimal distributed algorithm for recognizing mesh-connected networks

In this paper, we consider the problem of recognizing whether a given network is a rectangular mesh. We present an efficient distributed algorithm with an O(N) message and time complexity, where N is the number of nodes in the network. This is an improvement of a previous algorithm presented in Mohan (1990) with a message complexity of O(N log N) and time complexity of O(N^1.6). The proposed algorithm is constructive in nature and also assigns coordinates to the nodes of the network.     

Pyramidal thinning algorithm for SIMD parallel machines

We propose a parallel thinning algorithm for binary pictures. Given an N × N binary image including an object, our algorithm computes in O(N²) the skeleton of the object, using a pyramidal decomposition of the picture. The behavior of this algorithm is studied considering a family of digitalization of the same object at a different level of resolution. With the Exclusive Read Exclusive Write (EREW) Parallel Random Access Machine (PRAM), our algorithm runs in O(log N) time using O(N²/logN) processors and it is work-optimal. The same result is obtained with high-connectivity distributed memory SIMD machines having strong hypercube and pyramid. We describe the basic operator, the pyramidal algorithm and some experimental results on the SIMD MasPar parallel machine.     

Parallel processing approaches to edge relaxation

This paper describes several parallel algorithms for image edge relaxation on array processors with different numbers of processing elements (PEs) connected by a mesh or hypercube network. The time complexity of Prager's original edge relaxation scheme is O(N²) per iteration using floating-point operations on a sequential machine, where N² is the number of pixels in the image. Modifications to the scheme are made so that no multiplications are employed and only integer operations are required. Moreover, with parallel processing, the time complexity per iteration is reduced to some constant value. A time complexity analysis on two parallel algorithms is performed. Although the algorithm on an array processor with 4N² PEs achieved higher degree of parallelism, the algorithm with N² PEs is preferred. Further modifications on the latter algorithm are made to accommodate to fewer PEs.     

Parallel algorithms for solving the satisfaction problem of functional and multivalued data dependencies

Parallel algorithms for solving the satisfaction problem of non-trivial functional and multivalued data dependencies (FDs and MVDs) in a relation of N tuples by M processors are developed in this paper. Algorithms performing, in a parallel manner, batch or interactive checking of these data dependencies are also discussed. The M processors are organized as a linear systolic array. The time complexities of the first two algorithms for solving the FD satisfaction problem under M N are both O(N), and that of Algorithm (3) or (4) for solving the FD or MVD satisfaction problem under N M is O(N²/M). The latter complexity reduced to O(N) if N = M and is at least not worse than O(N log N) if N = M (N/log N).     

Distributed selectsort sorting algorithms on broadcast communication networks

In this paper, a distributed selectsort algorithm and a parameterized selectsort algorithm are presented to be applied on distributed systems for cases when N P where N is the number of elements to be sorted and P is the number of processors in the system. The distributed system considered in this paper uses a broadcasting channel for communication between processors. We show that the number of messages required for the parameterized selectsort algorithm is independent of N and is of complexity O(P), which is optimal in a distributed system with P processors. Furthermore, the amount of communication required in terms of elements is N + O(P³) and the computation time complexity is O((N/P)lgN + P²lg(N/P)). Hence, when N P³, the computation time complexity is O((N/P)lgN), which is optimal using P processors. In addition, this parameterized algorithm provides us with a parameter K such that by choosing the value of K allows us to trade among processing requirement, memory requirement, and communication requirement. It is shown that this parameterized algorithm can reduce the communication requirements significantly while only slightly increasing the computation requirements.     

Efficient algorithms for shortest distance queries on special classes of polygons

The problem of finding a rectilinear minimum bend path (RMBP) between two designated points inside a rectilinear polygon has applications in robotics and motion planning. In this paper, we present efficient algorithms to solve the query version of the RMBP problem for special classes of rectilinear polygons given their visibility graphs. Specifically, we show that given an unweighted graph G = (V, E), with ¦V¦ = N and ¦E¦ = M, algorithms to preprocess G in linear space and time such that the shortest distance queries — queries asking for the distance between any pair of nodes in the graph — can be answered in constant time and space are presented in this paper. For the case of a chordal graph G, our algorithms give a distance which is at most one away from the actual shortest distance. When G is a K-chordal graph, our algorithm produces an exact shortest distance in O(K) time. We also present a non-trivial parallel implementation of the sequential preprocessing algorithm for the CREW-PRAM model which runs in O(log² N) time using O(N + M) processors. After the preprocessing, we can answer the queries in constant time using a single processor.     

Comparison of Ecosystem Respiration Models based on Remote Sensing Data

Ecosystem respiration (Re) is an important component of terrestrial ecosystem carbon budget, and it was important to simulate Re accurately. In this study, Re was simulated at daily and 8-day time scales at 24 flux sites (52 site years) including 5 vegetation types by using three typical ecological models established based on remote sensing data, C-flux (the carbon flux model), ReRSM (Ecosystem respiration Remote Sensing Model) and TPGPP (Temperature Precipitation Gross Primary Production) model. Results showed that the three models had different performances. At 52 site years, the ranges of R² and RMSE were 0.72~0.96 and 0.30~3.47 gCm^-2d^-1 for the C-flux model, 0.70~0.98 and 0.45~6.07 gCm^-2d^-1 for the ReRSM model, and 0.76~0.97 and 0.41~2.45 gCm^-2d^-1 for the TPGPP model. The TPGPP performed best compared with the other two models. R² simulated with the TPGPP model was higher than the other two models at most site years with proportions of 73% and 67% at daily and 8-day scale, respectively. At daily and 8-day scale, R² simulated with the ReRSM model was higher than that with the C-flux model at most site years with proportions of 75% and 77%, while RMSE with ReRSM model was higher than that with the C-flux model at most site years with proportions of 79% and 76%, respectively. Results indicated that the ReRSM model could simulate the trends of seasonal variations of Re while model parameters had some uncertainties. One important parameter in the ReRSM model, LSWI_sm (Mean annual growing season of land surface water index), which was much lower would result in overestimation of Re, and higher LSWI_sm would result in Re underestimation.     

基于遥感和站点观测数据的生态系统呼吸模型比较

生态系统呼吸(Ecosystem respiration,Re)是陆地生态系统碳收支的重要组成部分,准确模拟Re对研究碳循环具有重要意义。利用3种典型的遥感模型,C-flux(The carbon flux model)、ReRSM(Ecosystem respiration Remote Sensing Model)和TPGPP(Temperature Precipitation Gross Primary Production)模型,基于不同时间尺度(1 d和8 d尺度)的通量观测和遥感数据,对包含5种植被类型(农作物CROP、落叶阔叶林DBF、常绿针叶林ENF、草地GRASS和混交林MF)的24个站点(52个站年)的Re进行了模拟。结果表明:不同模型模拟结果的差异较大,C-Flux模型模拟结果R2和RMSE的范围为0.72~0.96 gCm^-2d^-1和0.30~3.47 gCm^-2d^-1,ReRSM模型R2与RMSE的范围为0.70~0.98 gCm^-2d^-1和0.45~6.07 gCm^-2d^-1,TPGPP模型R2与RMSE的范围为0.76~0.97gCm^-2d^-1和0.41~2.45 gCm^-2d^-1;1 d和8 d尺度,TPGPP模型模拟效果最好,分别73%和67%的站年的TPGPP模型模拟结果的R2高于其他两种模型,65%和50%的站年的TPGPP模型模拟结果的RMSE低于另两种模型。大部分站年(分别为75%和77%)ReRSM模型模拟的Re与观测Re之间的R2明显高于C-flux模型,然而大部分站年(79%和77%)的RMSE高于C-flux模型,这表明ReRSM模型结构合理,能较好地模拟Re的季节变化趋势但模型参数有待改进。ReRSM模型中,年均生长季平均LSWI(Mean annual growing season of Land surface water index,LSWIsm)与其他站年相比过低,会导致模拟的Re高估,反之则低估。     

基于光学与SAR因子的森林生物量多元回归估算

基于福建省Landsat-8 OLI影像，利用混合像元分解模型从实测样地数据中筛选出“纯净”的植被像元，并将筛选出的样地分为针叶林、阔叶林和混交林3种植被类型，依次提取3种不同植被类型“纯净”植被像元的树高、林龄、坡度属性信息以及对应的光学NDVI、RVI植被因子和合成孔径雷达（SAR）HH、HV极化后向散射因子，分别构成不同植被类型的“含光学特征多元因子”（NDVI、RVI、树高、林龄、坡度）和“含SAR特征多元因子”（HH、HV、树高、林龄、坡度），开展对比研究。采用含光学特征的多元因子回归模型先估测不同植被类型的森林叶生物量，然后根据叶生物量与地上生物量的关系间接估测森林地上生物量。同时，采用含SAR特征的多元因子回归模型直接估测森林的地上生物量。最后，对比分析这两组多元回归模型的估测精度。结果表明：不同植被类型的含光学特征多元回归模型的验证精度（针叶林：R²为0.483，RMSE为29.522 t/hm²；阔叶林：R²为0.470，RMSE为21.632 t/hm²；混交林：R²为0.351，RSME为25.253 t/hm²）比含SAR特征多元回归模型的验证精度（针叶林：R²为0.319，RMSE为28.352 t/hm²；阔叶林：R²为0.353，RMSE为18.991t/hm²；混交林：R²为0.281，RMSE为26.637 t/hm²）略高，说明在福建省森林生物量估算中采用含光学特征的多元回归模型（先估测叶生物量进而间接估测地上生物量）比利用含SAR特征的多元回归模型（直接估测地上生物量）更具优势。     

基于光学与SAR因子的森林生物量多元回归估算

基于福建省Landsat-8 OLI影像,利用混合像元分解模型从实测样地数据中筛选出“纯净”的植被像元,并将筛选出的样地分为针叶林、阔叶林和混交林3种植被类型,依次提取3种不同植被类型“纯净”植被像元的树高、林龄、坡度属性信息以及对应的光学NDVI、RVI植被因子和合成孔径雷达（SAR）HH、HV极化后向散射因子,分别构成不同植被类型的“含光学特征多元因子”（NDVI、RVI、树高、林龄、坡度）和“含SAR特征多元因子”（HH、HV、树高、林龄、坡度）,开展对比研究。采用含光学特征的多元因子回归模型先估测不同植被类型的森林叶生物量,然后根据叶生物量与地上生物量的关系间接估测森林地上生物量。同时,采用含SAR特征的多元因子回归模型直接估测森林的地上生物量。最后,对比分析这两组多元回归模型的估测精度。结果表明：不同植被类型的含光学特征多元回归模型的验证精度（针叶林：R²为0.483,RMSE为29.522 t/hm²;阔叶林：R²为0.470,RMSE为21.632 t/hm²;混交林：R²为0.351,RSME为25.253 t/hm²）比含SAR特征多元回归模型的验证精度（针叶林：R²为0.319,RMSE为28.352 t/hm²;阔叶林：R²为0.353,RMSE为18.991t/hm²;混交林：R²为0.281,RMSE为26.637 t/hm²）略高,说明在福建省森林生物量估算中采用含光学特征的多元回归模型（先估测叶生物量进而间接估测地上生物量）比利用含SAR特征的多元回归模型（直接估测地上生物量）更具优势。     

Parallel clustering algorithms

Clustering techniques play an important role in exploratory pattern analysis, unsupervised learning and image segmentation applications. Many clustering algorithms, both partitional clustering and hierarchical clustering, require intensive computation, even for a modest number of patterns. This paper presents two parallel clustering algorithms. For a clustering problem with N = 2ⁿ patterns and M = 2^m features, the time complexity of the traditional partitional clustering algorithm on a single processor computer is O(MNK), where K is the number of clusters. The proposed algorithm on anSIMD computer with MN processors has a time complexity O(K(n + m)). The time complexity of the proposed single-link hierarchical clustering algorithm is reduced from O(MN²) of the uniprocessor algorithm to O(nN) with MN processors.     

Maximal intersection of spherical polygons by an arc with applications to 4-axis machining

Many geometric optimization problems in CAD/CAM can be reduced to a maximal intersection problem on the sphere: given a set of N simple spherical polygons on the unit sphere and a real number constant L≤2π, find an arc of length L on the unit sphere that intersects as many spherical polygons as possible. Past results can only solve this maximization problem for two very restricted special cases: the arc must be either a great circle or a semi-great circle. In this paper, a simple and deterministic algorithm based on domain partitioning is presented for solving this maximal arc intersection problem in the general case when the number L is arbitrary. The algorithm is made possible by reducing the domain of the arcs to a continuous sub-space in R² and then establishing a quotient space partitioning in this sub-space based on a congruence relation. The number of the constituting congruent sub-regions in this quotient space partitioning is shown to have an upper-bound O(E³), where E is the total number of edges on the polygons. The proposed algorithm has a worst-case upper bound O(ME) on its running time, where M is an output-sensitive number and is bounded by O(E³). Examples including two realistic tests for 4-axis NC machining are presented.     

基于TROPOMI叶绿素荧光遥感的冬小麦旱情监测

针对太阳诱导叶绿素荧光（Solar-Induced chlorophyll Fluorescence, SIF）可以有效指示陆表植被水分胁迫的特点,提出了归一化叶绿素荧光干旱指数（Normalized SIF Drought Index, NSDI）用于黄淮海地区冬小麦旱情监测。该方法首先基于哨兵-5p卫星（Sentinel-5p）对流层观测仪（Tropospheric Monitoring Instrument, TROPOMI）传感器反演得到的SIF原始产品集,通过0.1°等经纬步长栅格化处理为空间连续数据,然后基于时间序列分析进行了缺失值线性插补,再经过S-G滤波重建获得了高时空分辨率荧光数据集。以此数据集为基础,结合研究区冬小麦分布数据构建NSDI指数。通过选取典型旱情事件对比分析,NSDI指数与同期归一化植被指数（Normalized Difference Vegetation Index, NDVI）以及温度植被干旱指数（Temperature Vegetation Drought Index, TVDI）都有良好的相关性,其中与NDVI的R²为0.60,与TVDI的R²为0.41;NSDI指数与野外土壤水分调查结果也高度相关,其中河北样区R²为0.53,山东样区R²为0.54,整体R²为0.51;通过物联网监测数据分析显示,NSDI指数可以在优于2 d的滞后期内响应旱情的变化,其变化趋势与田间土壤水分保持高度相关。实验结果表明：NSDI指数可以在时空尺度上有效指示黄淮海地区冬小麦旱情。     

Spacetime-minimal systolic arrays for Gaussian elimination and the Algebraic path problem

In this paper, we derive time-minimal systolic arrays for Gaussian elimination and the Algebraic Path Problem (APP) that use a minimal number of processors. For a problem of size n, we obtain an execution time T(n) = 3n −1 using A(n) = n²/4+O(n) processors for Gaussian elimination, and T(n) = 5n −2 and A(n) = n³/+O(n) for the APP.