A 2n−2 step algorithm for routing in ann ×n array with constant-size queues

In this paper we describe a deterministic algorithm for solving any 1–1 packet-routing problem on ann ×n mesh in 2n–2 steps using constant-size queues. The time bound is optimal in the worst case. The best previous deterministic algorithm for this problem required time 2n+(n/q) using queues of size (q) for any 1qn, and the best previous randomized algorithm required time 2n+(logn) using constant-size queues.This research was supported by the Clear Center at UTD, DARPA Contracts N00014-91-J-1698 and N00014-92-J-1799, Air Force Contract F49620-92-J-0125, Army Contract DAAL-03-86-K-0171, an NSF Presidential Young Investigator Award with matching funds from AT&T and IBM, and by the Texas Advanced Research Program under Grant No. 3972. A preliminary version of this paper appeared in [5].     

High Order Numerical Discretization for Hamilton–Jacobi Equations on Triangular Meshes

In this paper we construct several numerical approximations for first order Hamilton–Jacobi equations on triangular meshes. We show that, thanks to a filtering procedure, the high order versions are non-oscillatory in the sense of satisfying the maximum principle. The methods are based on the first order Lax–Friedrichs scheme [2] which is improved here adjusting the dissipation term. The resulting first order scheme is -monotonic (we explain the expression in the paper) and converges to the viscosity solution as for the L -norm. The first high order method is directly inspired by the ENO philosophy in the sense where we use the monotonic Lax–Friedrichs Hamiltonian to reconstruct our numerical solutions. The second high order method combines a spatial high order discretization with the classical high order Runge–Kutta algorithm for the time discretization. Numerical experiments are performed for general Hamiltonians and L ¹, L ² and L -errors with convergence rates calculated in one and two space dimensions show the k-th order rate when piecewise polynomial of degree k functions are used, measured in L ¹-norm.     

Discrete Helmholtz–Hodge Decomposition on Polyhedral Meshes Using Compatible Discrete Operators

This article provides a methodology to perform discrete Helmholtz–Hodge decomposition on three-dimensional polyhedral meshes using structure-preserving schemes: the Compatible Discrete Operator schemes. We propose to extract the decomposition components independently with one equation to solve per component or potential. The key of the method is the choice of a discrete Hodge operator that makes a compromise between convergence rate and computational cost. Numerical experiments are performed to evaluate the convergence rate and the computational cost on various polyhedral meshes, in particular, on the FVCA benchmark meshes. We also investigate some linear solver capabilities to solve our equations. The main contribution of this paper is the application of the CDO schemes to the Hodge decomposition and the required solvers.     

Second-Order Accurate Godunov Scheme for Multicomponent Flows on Moving Triangular Meshes

This paper presents a second-order accurate adaptive Godunov method for two-dimensional (2D) compressible multicomponent flows, which is an extension of the previous adaptive moving mesh method of Tang et al. (SIAM J. Numer. Anal. 41:487–515, 2003) to unstructured triangular meshes in place of the structured quadrangular meshes. The current algorithm solves the governing equations of 2D multicomponent flows and the finite-volume approximations of the mesh equations by a fully conservative, second-order accurate Godunov scheme and a relaxed Jacobi-type iteration, respectively. The geometry-based conservative interpolation is employed to remap the solutions from the old mesh to the newly resulting mesh, and a simple slope limiter and a new monitor function are chosen to obtain oscillation-free solutions, and track and resolve both small, local, and large solution gradients automatically. Several numerical experiments are conducted to demonstrate robustness and efficiency of the proposed method. They are a quasi-2D Riemann problem, the double-Mach reflection problem, the forward facing step problem, and two shock wave and bubble interaction problems.     

一类n×n矩阵博弈的Nash均衡的近似计算

给出了一种求解某类n×n矩阵博弈Nash均衡的近似解的算法。通过剖分单纯形,将混合策略空间离散化,利用初始的单纯形根据标号函数和替换规则求出此类矩阵博弈Nash均衡的近似解。并分析了其最优解与近似解的计算误差。     

Analysis of the Finite Element Method for the Laplace–Beltrami Equation on Surfaces with Regions of High Curvature Using Graded Meshes

We derive error estimates for the piecewise linear finite element approximation of the Laplace–Beltrami operator on a bounded, orientable, \(C^3\), surface without boundary on general shape regular meshes. As an application, we consider a problem where the domain is split into two regions: one which has relatively high curvature and one that has low curvature. Using a graded mesh we prove error estimates that do not depend on the curvature on the high curvature region. Numerical experiments are provided.     

Remarks on “A Synthesis of Several Sorting Algorithms” by John Darlington

Summary In his paper A Synthesis of Several Sorting Algorithms, John Darlington presents syntheses for six different sorting algorithms, together with a family tree of sorting algorithms, and mentions a symmetry between Quick Sort, Selection Sort, Merge Sort, and Insertion Sort. In our own attempts to codify programming knowledge, we have developed a slightly different family tree which shows similar symmetries, and which also shows that Bubble Sort and Sinking Sort can be viewed as in-place versions of Selection Sort and Insertion Sort, thus adding another symmetry to those noted by Darlington.     

Maximum-Principle-Satisfying and Positivity-Preserving High Order Discontinuous Galerkin Schemes for?Conservation Laws on Triangular Meshes

In Zhang and Shu (J. Comput. Phys. 229:3091–3120, 2010), two of the authors constructed uniformly high order accurate finite volume and discontinuous Galerkin (DG) schemes satisfying a strict maximum principle for scalar conservation laws on rectangular meshes. The technique is generalized to positivity preserving (of density and pressure) high order DG or finite volume schemes for compressible Euler equations in Zhang and Shu (J. Comput. Phys. 229:8918–8934, 2010). The extension of these schemes to triangular meshes is conceptually plausible but highly nontrivial. In this paper, we first introduce a special quadrature rule which is exact for two-variable polynomials over a triangle of a given degree and satisfy a few other conditions, by which we can construct high order maximum principle satisfying finite volume schemes (e.g. essentially non-oscillatory (ENO) or weighted ENO (WENO) schemes) or DG method solving two dimensional scalar conservation laws on triangular meshes. The same method can preserve the maximum principle for DG or finite volume schemes solving two-dimensional incompressible Euler equations in the vorticity stream-function formulation, or any passive convection equation with an incompressible velocity field. We also obtain positivity preserving (for density and pressure) high order DG or finite volume schemes solving compressible Euler equations on triangular meshes. Numerical tests for the third order Runge-Kutta DG (RKDG) method on unstructured meshes are reported.     

Distance three labellings for K n ×K 2

In a wireless communication network, the channel assignment problem addresses the correct assignment of a frequency to each transmitter in the network. To avoid interference between two nearby transmitters, the assigned frequencies must satisfy certain conditions related to the distance between transmitters. We can use only a limited number of channels; hence, we have to minimize the range of frequencies used. The distance labelling of a graph is a mathematical model of the channel assignment problem derived from the work of Hale [Frequency assignment: Theory and application, Proc. IEEE 68 (1980), pp. 1497–1514]. Lam et al. [L(j, k)-labelings for the products of complete graphs, J. Comb. Optim. 14 (2007), pp. 219–227] addressed distance two labelling for the direct product K _n ×K _m of complete graphs K _n and K _m . In this paper, we solve the distance three labelling problem for K _n ×K ₂.     

n×m加工系统的托盘调度优化

本文通过对 G.Cohen 给出的 n×m 的加工系统 Z 域模型加以改进,即选择工件的输入时间和输出时间分别作输入变量和输出变量,利用矩阵与事件图的关系,研究闭环系统反馈对系统矩阵的影响,并由此给出一个保证闭环系统具有最小特征值前提下选择最少托盘数量的优化算法,即托盘的优化调度算法.     

An Improved HEAPSORT Algorithm with n log n - 0.788928n Comparisons in the Worst Case

A new variant of HEAPSORT is presented in this paper. The algorithm is not an internal sorting algorithm in the strong sense, since extra storage for n integers is necessary. The basic idea of the new algorithm is similar to the classical sorting algorithm HEAPSORT, but the algorithm rebuilds the heap in another way. The basic idea of the new algorithm is it uses only one comparison at each node. The new algorithm shift walks down a path in the heap until a leaf is reached. The request of placing the element in the root immediately to its destination is relaxed. The new algorithm requires about n log n - 0.788928n comparisons in the worst case and n log n - n comparisons on the average which is only about 0.4n more than necessary. It beats on average even the clever variants of QUICKSORT, if n is not very small. The difference between the worst case and the best case indicates that there is still room for improvement of the new algorithm by constructing heap more carefully.     

A parallel O(log n) algorithm for the drawing of algebraic curves in an n × n square

A parallel O(log n) algorithm for the drawing of algebraic curves in the digital plane is described. The algorithm contains a systolic subroutine and is implemented in a parallel computer structure called pyramid cellular automaton (PCA). The constructibility of conics and especially of circles (Sakoda's (1981) circle problem) in O(log n) time follows as a special case.     

Wireless-N和Connect with Centrino 英特尔802.11n产品

本刊讯1月24日,英特尔公司推出其下一代Wireless-N网络连接。英特尔Wireless-N网络连接基于802.11n Wi-Fi规范草案,这款网络连接可为用户提供最多五倍的性能,并将无线覆盖范围扩大到原来的两倍,同时与现有的基于802.11n草案标准的产品相比,能够额外多提供一个小时的笔记本电脑续航时间。Wireless-N产品能够减少家庭中的“盲点”;为用户带来逼真的高清晰(HD)娱乐体验(如高清晰视频流电影);提升电池使用寿命,并可与现有802.11a/b/g接入点相兼容。当与采用英特尔迅驰双核移动计算技术,并运行Wireless-N的系统结合使用时,英特尔酷睿2双核处…     

θ(1) Time Algorithm for Structural Characterization of Multi-Leveled Images and its Applications on a Reconfigurable Mesh Computer

Given a multi-leveled image of size n × n, stored in a reconfigurable mesh computer of the same size one point per processing element (PE). In this paper, we propose a parallel algorithm for structural characterization of all the components of the image. The algorithm is based on the representation of component contour by straight line segments to reduce the volume of data processing. The resulted contours are simultaneously processed using the contour running approach. The pertinent data obtained after the component characterization are used in the filtering application and to develop an algorithm for the convex hull search for all the image components. Our algorithm is assigned to be implemented on a reconfigurable mesh computer and is of θ(1) time complexity.     

Research on Network Architecture with Trustworthiness and Controllability

In this paper, the architecture of trustworthy and controllable networks is discussed to meet arising application requirements. After reviewing the lessons and experiences of success and failure in the Internet and summarizing related work, we analyze the basic targets of providing trustworthiness and controllability. Then, the anticipant architecture is introduced. Based on the resulting design, several trustworthy and controllable mechanisms are also discussed.     

Visual interference with users’ tasks on multiwindow systems

This study investigated the potential visual interference imposed by displayed peripheral windows that are not central to a user's current task performance. In particular, the study examined the relation between foveal vision and peripheral vision activities in multiwindow systems. It was suggested that the number and layout of the windows in a multiwindow system can interfere with a user's activities while performing a task. Results from a visual search experiment were indicated as follows:

1. Displayed peripheral windows interfered with a user's current task performance.

2. The number of the peripheral windows is a significant factor in the interference.

3. The types of the layout, overlapping or nonoverlapping, are also a significant factor in the interference.

4. The activities of the foveal vision get worse when the visual position of the task performance is closer to the peripheral windows.

5. These factors have different influences depending on whether the peripheral windows are static or dynamic

We discuss these results from the viewpoint of the nature of the human visual systems, especially the relation between foveal and peripheral vision.