Dynamic Multicast Session Provisioning in WDM Optical Networks with Sparse Splitting Capability

In this work, we study dynamic provisioning of multicast sessions in a wavelength-routed sparse splitting capable WDM network with an arbitrary mesh topology where the network consists of nodes with full, partial, or no wavelength conversion capabilities and a node can be a tap-and-continue (TaC) node or a splitting and delivery (SaD) node. The objectives are to minimize the network resources in terms of wavelength-links used by each session and to reduce the multicast session blocking probability. The problem is to route the multicast session from each source to the members of every multicast session, and to assign an appropriate wavelength to each link used by the session. We propose an efficient online algorithm for dynamic multicast session provisioning. To evaluate the proposed algorithm, we apply the integer linear programming (ILP) optimization tool on a per multicast session basis to solve off-line the optimal routing and wavelength assignment given a multicast session and the current network topology as well as its residual network resource information. We formulate the per session multicast routing and wavelength assignment problem as an ILP. With this ILP formulation, the multicast session blocking probability or success probability can then be estimated based on solving a series of ILPs off-line. We have evaluated the effectiveness of the proposed online algorithm via simulation in terms of session blocking probability and network resources used by a session. Simulation results indicate that our proposed computationally efficient online algorithm performs well even when a fraction of the nodes are SaD nodes.     

The Computational Complexity of the Chow Form

We present a bounded probability algorithm for the computation of the Chowforms of the equidimensional components of an algebraic variety. In particular, this gives an alternative procedure for the effective equidimensional decomposition of the variety, since each equidimensional component is characterized by its Chow form. The expected complexity of the algorithm is polynomial in the size and the geometric degree of the input equation system defining the variety. Hence it improves (or meets in some special cases) the complexity of all previous algorithms for computing Chow forms. In addition to this, we clarify the probability and uniformity aspects, which constitutes a further contribution of the paper. The algorithm is based on elimination theory techniques, in line with the geometric resolution algorithm due to M. Giusti, J. Heintz, L. M. Pardo, and their collaborators. In fact, ours can be considered as an extension of their algorithm for zero-dimensional systems to the case of positive-dimensional varieties. The key element for dealing with positive-dimensional varieties is a new Poisson-type product formula. This formula allows us to compute the Chow form of an equidimensional variety from a suitable zero-dimensional fiber. As an application, we obtain an algorithm to compute a subclass of sparse resultants, whose complexity is polynomial in the dimension and the volume of the input set of exponents. As another application, we derive an algorithm for the computation of the (unique) solution of a generic overdetermined polynomial equation system.     

Probabilistic linear models for multiresolution estimation in gray-level images

A multiresolution analysis of digital gray-level images is presented. A gray-level multi-scale framework is determined from two main assumptions: the gray scale is binary at the finest spatial resolution, and the gray levels of composed regions are obtained additively. In order to interrelate the gray-level histograms of the same image at different resolutions, probabilistic linear models are developed, which are then applied for estimation. Linear-optimization theory is used as a way of constructing such models. A general procedure for image processing is sketched, based on gray-level estimation. A versatile algorithm for nonlinear filtering is derived. Some examples of prospective applications are given.This work was partially supported by grant TIC91-646 from the DGYCIT of the Spanish Government.     

Sparse-grid finite-volume multigrid for 3D-problems

We introduce a multigrid algorithm for the solution of a second order elliptic equation in three dimensions. For the approximation of the solution we use a partially ordered hierarchy of finite-volume discretisations. We show that there is a relation with semicoarsening and approximation by more-dimensional Haar wavelets. By taking a proper subset of all possible meshes in the hierarchy, a sparse grid finite-volume discretisation can be constructed.The multigrid algorithm consists of a simple damped point-Jacobi relaxation as the smoothing procedure, while the coarse grid correction is made by interpolation from several coarser grid levels.The combination of sparse grids and multigrid with semi-coarsening leads to a relatively small number of degrees of freedom,N, to obtain an accurate approximation, together with anO(N) method for the solution. The algorithm is symmetric with respect to the three coordinate directions and it is fit for combination with adaptive techniques.To analyse the convergence of the multigrid algorithm we develop the necessary Fourier analysis tools. All techniques, designed for 3D-problems, can also be applied for the 2D case, and — for simplicity — we apply the tools to study the convergence behaviour for the anisotropic Poisson equation for this 2D case.     

Optimized analysis of the critical behavior in polymer mixtures from Monte Carlo simulations

A complete outline is given for how to determine the critical properties of polymer mixtures with extrapolation methods similar to the Ferrenberg-Swendsen techniques recently devised for spin systems. By measuring not only averages but the whole distribution of the quantities of interest, it is possible to extrapolate the data obtained in only a few simulations nearT _c over the entire critical region, thereby saving at least 90% of the computer time normally needed to locate susceptibility peaks or cumulant intersections and still getting more precise results. A complete picture of the critical properties of polymer mixtures in the thermodynamic limit is then obtained with finite-size scaling functions. Since the amount of information extracted from a simulation in this way is drastically increased as compared to conventional methods, the investigation of mixtures with long chains or built-in asymmetries is now possible. As an example, the critical points, exponents, and amplitudes of dense, symmetric polymer mixtures with chain lengths ranging fromN=16 up toN=256 are determined within the framework of the 3D bond fluctuation model using grand canonical simulation techniques. As an example for an asymmetry, the generalization of the method to asymmetric monomer potentials is briefly discussed.     

基于FPGA的图像自适应AWB系统设计与实现

为了解决常见自动白平衡(Auto White Balance, AWB)方法的场景适应能力不足且实时性较差等问题,提出了一种基于颜色通道直方图重构的自适应AWB方法,并使用现场可编程门阵列(FPGA)对所提出的算法进行硬件电路实现,在校正图像白平衡的同时也确保了系统高速实时处理图像。首先对图像进行限制对比度自适应直方图均衡化(CLAHE)处理来提高图像对比度,然后对图像进行灰度级区间的通道分区统计,对不同场景类别的图像采用颜色直方图匹配或平移的重构方式做自适应处理。实验结果表明,该算法在处理图像白平衡时,相比基于光源估计的AWB算法,色温校正准确率提高了14%,对不同色彩场景有更好的适应性,具有实时处理能力。     

On solving sparse band systems with three algorithms of the ABS family

In this paper, we examine three algorithms in the ABS family and consider their storage requirements on sparse band systems. It is shown that, when using the implicit Cholesky algorithm on a band matrix with band width 2q+1, onlyq additional vectors are required. Indeed, for any matrix with upper band widthq, onlyq additional vectors are needed. More generally, ifa _kj 0,j>k, then thejth row ofH _i is effectively nonzero ifj>i>k. The arithmetic operations involved in solving a band matrix by this method are dominated by (1/2)n ² q. Special results are obtained forq-band tridiagonal matrices and cyclic band matrices.The implicit Cholesky algorithm may require pivoting if the matrixA does not possess positive-definite principal minors, so two further algorithms were considered that do not require this property. When using the implicit QR algorithm, a matrix with band widthq needs at most 2q additional vectors. Similar results forq-band tridiagonal matrices and cyclic band matrices are obtained.For the symmetric Huang algorithm, a matrix with band widthq requiresq–1 additional vectors. The storage required forq-band tridiagonal matrices and cyclic band matrices are again analyzed.This work was undertaken during the visit of Dr. J. Abaffy to Hatfield Polytechnic, sponsored by SERC Grant No. GR/E-07760.     

Parallel GMRES solver for fast analysis of large linear dynamic systems on GPU platforms

In this paper, we propose an efficient parallel dynamic linear solver, called GPU-GMRES, for transient analysis of large linear dynamic systems such as large power grid networks. The new method is based on the preconditioned generalized minimum residual (GMRES) iterative method implemented on heterogeneous CPU–GPU platforms. The new solver is very robust and can be applied to power grids with different structures as well as for general analysis problems for large linear dynamic systems with asymmetric matrices. The proposed GPU-GMRES solver adopts the very general and robust incomplete LU based preconditioner. We show that by properly selecting the right amount of fill-ins in the incomplete LU factors, a good trade-off between GPU efficiency and convergence rate can be achieved for the best overall performance. Such tunable feature can make this algorithm very adaptive to different problems. GPU-GMRES solver properly partitions the major computing tasks in GMRES solver to minimize the data traffic between CPU and GPUs to enhance performance of the proposed method. Furthermore, we propose a new fast parallel sparse matrix–vector (SpMV) multiplication algorithm to further accelerate the GPU-GMRES solver. The new algorithm, called segSpMV, can enjoy full coalesced memory access compared to existing approaches. To further improve the scalability and efficiency, segSpMV method is further extended to multi-GPU platforms, which leads to more scalable and faster multi-GPU GMRES solver. Experimental results on the set of the published IBM benchmark circuits and mesh-structured power grid networks show that the GPU-GMRES solver can deliver order of magnitudes speedup over the direct LU solver, UMFPACK. The resulting multi-GPU-GMRES can also deliver 3–12× speedup over the CPU implementation of the same GMRES method on transient analysis.     

Sparse non-negative matrix factorizations for ultrasound factor analysis

Factor analysis is a powerful tool used for the analysis of dynamic studies. One of the major drawbacks of Factor Analysis of Dynamic Structures (FADS) is that the solution is not mathematically unique when only non-negativity constraints are used to determine factors and factor coefficients. In this paper, we introduce a novel method to correct FADS solutions by constructing and minimizing a new objective function. The method is improved from non-negative matrix factorizations (NMFs) algorithm by adding a sparse constraint that penalizes multiple components in the images of the factor coefficients. The technique is tested on computer simulations, and a patient ultrasound liver study. The results show that the method works well in comparison to the truth in computer simulations and to region of interest (ROI) measurements in the experimental studies.