The modeling of dynamical systems from a time series implemented by our DSA program introduces binary trees of height D with all leaves on the same level, and the related subtrees of height L 〈 D. These are called e-...The modeling of dynamical systems from a time series implemented by our DSA program introduces binary trees of height D with all leaves on the same level, and the related subtrees of height L 〈 D. These are called e-trees and e-subtrees. The recursive and nonrecursive versions of the traversal algorithms for the trees with dynamically created nodes are discussed. The original nonrecursive algorithms that return the pointer to the next node in preorder, inorder and postorder traversals are presented. The space-time complexity analysis shows and the execution time measurements confirm that for these O（2D） algorithms, the recursive versions have approximately 10-25% better time constants. Still, the use of nonrecursive algorithms may be more appropriate in several occasions.展开更多
Through the octree data structure analysis,a volumetric dataset of closed-cell porous materials is converted into a dataset of hierarchical octree nodes,and then the specific traversal search algorithm on the octree n...Through the octree data structure analysis,a volumetric dataset of closed-cell porous materials is converted into a dataset of hierarchical octree nodes,and then the specific traversal search algorithm on the octree nodes is depicted in details,which is involved in six steps of the volume growth model and one step of the volume decomposition model.Moreover,the conditions of both the proceeding traversal and three possibilities of terminating are given,and the traversal algorithm of completeness is proved from a theoretical perspective.Finally,using a simulated volumetric dataset of columnar pores,the extracting effectiveness of the octree traversal algorithm is verified.The results show that the volume and the distribution information of pores can be successfully extracted by the proposed algorithm,which builds a solid foundation for a more effective performance analysis of porous materials.展开更多
Extended Kalman Filter(EKF)algorithm is widely used in parameter estimation for nonlinear systems.The estimation precision is sensitively dependent on EKF’s initial state covariance matrix and state noise matrix.The ...Extended Kalman Filter(EKF)algorithm is widely used in parameter estimation for nonlinear systems.The estimation precision is sensitively dependent on EKF’s initial state covariance matrix and state noise matrix.The grid optimization method is always used to find proper initial matrix for off-line estimation.However,the grid method has the draw back being time consuming hence,coarse grid followed by a fine grid method is adopted.To further improve efficiency without the loss of estimation accuracy,we propose a genetic algorithm for the coarse grid optimization in this paper.It is recognized that the crossover rate and mutation rate are the main influencing factors for the performance of the genetic algorithm,so sensitivity experiments for these two factors are carried out and a set of genetic algorithm parameters with good adaptability were selected by testing with several gyros’experimental data.Experimental results show that the proposed algorithm has higher efficiency and better estimation accuracy than the traversing grid algorithm.展开更多
Breadth-first search(BFS) is an important kernel for graph traversal and has been used by many graph processing applications. Extensive studies have been devoted in boosting the performance of BFS. As the most effecti...Breadth-first search(BFS) is an important kernel for graph traversal and has been used by many graph processing applications. Extensive studies have been devoted in boosting the performance of BFS. As the most effective solution, GPU-acceleration achieves the state-of-the-art result of 3.3×109 traversed edges per second on a NVIDIA Tesla C2050 GPU. A novel vertex frontier based GPU BFS algorithm is proposed, and its main features are three-fold. Firstly, to obtain a better workload balance for irregular graphs, a virtual-queue task decomposition and mapping strategy is introduced for vertex frontier expanding. Secondly, a global deduplicate detection scheme is proposed to remove reduplicative vertices from vertex frontier effectively. Finally, a GPU-based bottom-up BFS approach is employed to process large frontier. The experimental results demonstrate that the algorithm can achieve 10% improvement over the state-of-the-art method on diverse graphs. Especially, it exhibits 2-3 times speedup on low-diameter and scale-free graphs over the state-of-the-art on a NVIDIA Tesla K20 c GPU, reaching a peak traversal rate of 11.2×109 edges/s.展开更多
文摘The modeling of dynamical systems from a time series implemented by our DSA program introduces binary trees of height D with all leaves on the same level, and the related subtrees of height L 〈 D. These are called e-trees and e-subtrees. The recursive and nonrecursive versions of the traversal algorithms for the trees with dynamically created nodes are discussed. The original nonrecursive algorithms that return the pointer to the next node in preorder, inorder and postorder traversals are presented. The space-time complexity analysis shows and the execution time measurements confirm that for these O（2D） algorithms, the recursive versions have approximately 10-25% better time constants. Still, the use of nonrecursive algorithms may be more appropriate in several occasions.
基金The National Basic Research Program of China(973Program)(No.2006CB601202)
文摘Through the octree data structure analysis,a volumetric dataset of closed-cell porous materials is converted into a dataset of hierarchical octree nodes,and then the specific traversal search algorithm on the octree nodes is depicted in details,which is involved in six steps of the volume growth model and one step of the volume decomposition model.Moreover,the conditions of both the proceeding traversal and three possibilities of terminating are given,and the traversal algorithm of completeness is proved from a theoretical perspective.Finally,using a simulated volumetric dataset of columnar pores,the extracting effectiveness of the octree traversal algorithm is verified.The results show that the volume and the distribution information of pores can be successfully extracted by the proposed algorithm,which builds a solid foundation for a more effective performance analysis of porous materials.
文摘Extended Kalman Filter(EKF)algorithm is widely used in parameter estimation for nonlinear systems.The estimation precision is sensitively dependent on EKF’s initial state covariance matrix and state noise matrix.The grid optimization method is always used to find proper initial matrix for off-line estimation.However,the grid method has the draw back being time consuming hence,coarse grid followed by a fine grid method is adopted.To further improve efficiency without the loss of estimation accuracy,we propose a genetic algorithm for the coarse grid optimization in this paper.It is recognized that the crossover rate and mutation rate are the main influencing factors for the performance of the genetic algorithm,so sensitivity experiments for these two factors are carried out and a set of genetic algorithm parameters with good adaptability were selected by testing with several gyros’experimental data.Experimental results show that the proposed algorithm has higher efficiency and better estimation accuracy than the traversing grid algorithm.
基金Projects(61272142,61103082,61003075,61170261,61103193)supported by the National Natural Science Foundation of ChinaProject supported by the Program for New Century Excellent Talents in University of ChinaProjects(2012AA01A301,2012AA010901)supported by the National High Technology Research and Development Program of China
文摘Breadth-first search(BFS) is an important kernel for graph traversal and has been used by many graph processing applications. Extensive studies have been devoted in boosting the performance of BFS. As the most effective solution, GPU-acceleration achieves the state-of-the-art result of 3.3×109 traversed edges per second on a NVIDIA Tesla C2050 GPU. A novel vertex frontier based GPU BFS algorithm is proposed, and its main features are three-fold. Firstly, to obtain a better workload balance for irregular graphs, a virtual-queue task decomposition and mapping strategy is introduced for vertex frontier expanding. Secondly, a global deduplicate detection scheme is proposed to remove reduplicative vertices from vertex frontier effectively. Finally, a GPU-based bottom-up BFS approach is employed to process large frontier. The experimental results demonstrate that the algorithm can achieve 10% improvement over the state-of-the-art method on diverse graphs. Especially, it exhibits 2-3 times speedup on low-diameter and scale-free graphs over the state-of-the-art on a NVIDIA Tesla K20 c GPU, reaching a peak traversal rate of 11.2×109 edges/s.
