We decompose the problem of the optimal multi-degree reduction of Bézier curves with corners constraint into two simpler subproblems, namely making high order interpolations at the two endpoints without degree re...We decompose the problem of the optimal multi-degree reduction of Bézier curves with corners constraint into two simpler subproblems, namely making high order interpolations at the two endpoints without degree reduction, and doing optimal degree reduction without making high order interpolations at the two endpoints. Further, we convert the second subproblem into multi-degree reduction of Jacobi polynomials. Then, we can easily derive the optimal solution using orthonormality of Jacobi polynomials and the least square method of unequally accurate measurement. This method of 'divide and conquer' has several advantages including maintaining high continuity at the two endpoints of the curve, doing multi-degree reduction only once, using explicit approximation expressions, estimating error in advance, low time cost, and high precision. More importantly, it is not only deduced simply and directly, but also can be easily extended to the degree reduction of surfaces. Finally, we present two examples to demonstrate the effectiveness of our algorithm.展开更多
SpeedShot,a dual camera high-speed imaging technology recently demonstrated by Zhang et al.,'demonstrates a 32×increase in effective frame rate by leveraging the motion gradient in frames captured by parallel...SpeedShot,a dual camera high-speed imaging technology recently demonstrated by Zhang et al.,'demonstrates a 32×increase in effective frame rate by leveraging the motion gradient in frames captured by parallel cameras.As interframe-motion estimation is the core element of most video compression algorithms,SpeedShot can be understood as a physical layer implementation of such an algorithm.Here,we seek to explain the context that makes SpeedShot interesting and to consider the roadmap for continuing improvements in camera information capacity.展开更多
Tools for pair-wise bio-sequence alignment have for long played a central role in computation biology. Several algorithms for bio-sequence alignment have been developed. The Smith-Waterman algorithm, based on dynamic ...Tools for pair-wise bio-sequence alignment have for long played a central role in computation biology. Several algorithms for bio-sequence alignment have been developed. The Smith-Waterman algorithm, based on dynamic programming, is considered the most fundamental alignment algorithm in bioinformatics. However the existing parallel Smith-Waterman algorithm needs large memory space, and this disadvantage limits the size of a sequence to be handled. As the data of biological sequences expand rapidly, the memory requirement of the existing parallel Smith- Waterman algorithm has become a critical problem. For solving this problem, we develop a new parallel bio-sequence alignment algorithm, using the strategy of divide and conquer, named PSW-DC algorithm. In our algorithm, first, we partition the query sequence into several subsequences and distribute them to every processor respectively, then compare each subsequence with the whole subject sequence in parallel, using the Smith-Waterman algorithm, and get an interim result, finally obtain the optimal alignment between the query sequence and subject sequence, through the special combination and extension method. Memory space required in our algorithm is reduced significantly in comparison with existing ones. We also develop a key technique of combination and extension, named the C&E method, to manipulate the interim results and obtain the final sequences alignment. We implement the new parallel bio-sequences alignment algorithm, the PSW-DC, in a cluster parallel system.展开更多
To take advantage of the multiuser diversity resulted from the variation in channel conditions among the users, it has become an interesting and challenging problem to efficiently allocate the resources such as subcar...To take advantage of the multiuser diversity resulted from the variation in channel conditions among the users, it has become an interesting and challenging problem to efficiently allocate the resources such as subcarriers, bits, and power. Most of current research concentrates on solving the resource-allocation problem for all users together in a centralized way, which brings about high computational complexity and makes it impractical for real system. Therefore, a coalitional game framework for downlink multi-user resource allocation in long term evolution （LTE） system is proposed, based on the divide-and-conquer idea. The goal is to maximize the overall system data rate under the constraints of each user＇s minimal rate requirement and maximal transmit power of base station while considering the fairness among users. In this framework, a coalitional formation algorithm is proposed to achieve optimal coalition formation and a two-user bargaining algorithm is designed to bargain channel assignment between two users. The total computational complexity is greatly reduced in comparison with conventional methods. The simulation results show that the proposed algorithms acquire a good tradeoff between the overall system throughout and fairness, compared to maximal rate and max-min schemes.展开更多
A divide-and-conquer strategy is given for embedding a distance-net point set into Euclidean space En, and the problem of embedding a bounded distance-net point set into E3 and its application to the macromolecular co...A divide-and-conquer strategy is given for embedding a distance-net point set into Euclidean space En, and the problem of embedding a bounded distance-net point set into E3 and its application to the macromolecular conformation with Nuclear Magnetic Resonance data are discussed.展开更多
基金supported by the National Natural Science Foundation of China (No. 60873111)the National Basic Research Program (973) of China (No. 2004CB719400)
文摘We decompose the problem of the optimal multi-degree reduction of Bézier curves with corners constraint into two simpler subproblems, namely making high order interpolations at the two endpoints without degree reduction, and doing optimal degree reduction without making high order interpolations at the two endpoints. Further, we convert the second subproblem into multi-degree reduction of Jacobi polynomials. Then, we can easily derive the optimal solution using orthonormality of Jacobi polynomials and the least square method of unequally accurate measurement. This method of 'divide and conquer' has several advantages including maintaining high continuity at the two endpoints of the curve, doing multi-degree reduction only once, using explicit approximation expressions, estimating error in advance, low time cost, and high precision. More importantly, it is not only deduced simply and directly, but also can be easily extended to the degree reduction of surfaces. Finally, we present two examples to demonstrate the effectiveness of our algorithm.
文摘SpeedShot,a dual camera high-speed imaging technology recently demonstrated by Zhang et al.,'demonstrates a 32×increase in effective frame rate by leveraging the motion gradient in frames captured by parallel cameras.As interframe-motion estimation is the core element of most video compression algorithms,SpeedShot can be understood as a physical layer implementation of such an algorithm.Here,we seek to explain the context that makes SpeedShot interesting and to consider the roadmap for continuing improvements in camera information capacity.
文摘Tools for pair-wise bio-sequence alignment have for long played a central role in computation biology. Several algorithms for bio-sequence alignment have been developed. The Smith-Waterman algorithm, based on dynamic programming, is considered the most fundamental alignment algorithm in bioinformatics. However the existing parallel Smith-Waterman algorithm needs large memory space, and this disadvantage limits the size of a sequence to be handled. As the data of biological sequences expand rapidly, the memory requirement of the existing parallel Smith- Waterman algorithm has become a critical problem. For solving this problem, we develop a new parallel bio-sequence alignment algorithm, using the strategy of divide and conquer, named PSW-DC algorithm. In our algorithm, first, we partition the query sequence into several subsequences and distribute them to every processor respectively, then compare each subsequence with the whole subject sequence in parallel, using the Smith-Waterman algorithm, and get an interim result, finally obtain the optimal alignment between the query sequence and subject sequence, through the special combination and extension method. Memory space required in our algorithm is reduced significantly in comparison with existing ones. We also develop a key technique of combination and extension, named the C&E method, to manipulate the interim results and obtain the final sequences alignment. We implement the new parallel bio-sequences alignment algorithm, the PSW-DC, in a cluster parallel system.
基金supported by the National Science and Technology Major Project(2011ZX03001-007-03)the National Natural Science Foundation of China(61271182)
文摘To take advantage of the multiuser diversity resulted from the variation in channel conditions among the users, it has become an interesting and challenging problem to efficiently allocate the resources such as subcarriers, bits, and power. Most of current research concentrates on solving the resource-allocation problem for all users together in a centralized way, which brings about high computational complexity and makes it impractical for real system. Therefore, a coalitional game framework for downlink multi-user resource allocation in long term evolution （LTE） system is proposed, based on the divide-and-conquer idea. The goal is to maximize the overall system data rate under the constraints of each user＇s minimal rate requirement and maximal transmit power of base station while considering the fairness among users. In this framework, a coalitional formation algorithm is proposed to achieve optimal coalition formation and a two-user bargaining algorithm is designed to bargain channel assignment between two users. The total computational complexity is greatly reduced in comparison with conventional methods. The simulation results show that the proposed algorithms acquire a good tradeoff between the overall system throughout and fairness, compared to maximal rate and max-min schemes.
基金Project supported by the National Natural Science Foundation of China.
文摘A divide-and-conquer strategy is given for embedding a distance-net point set into Euclidean space En, and the problem of embedding a bounded distance-net point set into E3 and its application to the macromolecular conformation with Nuclear Magnetic Resonance data are discussed.
