检索结果-内蒙古大学图书馆

Improving efficiency and cost of ordering algorithms in pathfinding using shell layers

EXPERT SYSTEMS WITH APPLICATIONS 2024年第PartD期238卷

作者： Allus, Abdullah Diab, Abdul Moati Bayraktar, Ertugrul Yildiz Tech Univ Dept Mechatron Engn TR-34349 Istanbul Turkiye

Optimal path planning is a fundamental problem in artificial intelligence (AI) and has wide applications in areas such as robotics, transportation, and logistics. In this paper, we propose a novel approach for ordering algorithms in pathfinding problems using the concept of shell layers. Our approach aims to improve the computational efficiency and distance cost of ordering algorithms. To evaluate the effectiveness of our approach, we compare it with five state-of-the-art techniques commonly used in the field of ordering algorithms on eight different scenarios with varying configurations. Our results show that our proposed approach outperformed the state-of-the-art techniques in terms of time-computational complexity and distance cost in most of the scenarios, demonstrating its potential as a new state-of-the-art technique for ordering algorithms. Specifically, our approach outperformed the nearest neighbor, A*, branch and bound, Christofides, and genetics ordering algorithms. However, we also identified two specific situations where our approach was outperformed by two state-of-the-art algorithms due to the specific distribution of the goal nodes. These findings highlight the importance of evaluating and comparing ordering algorithms in various scenarios. Our approach has significant implications for AI research and development, as it has the potential to improve the performance of pathfinding algorithms in various applications. We also discuss the limitations of our approach and potential areas for further research, such as investigating the effectiveness of our approach in different types of graphs and exploring the potential use of machine learning techniques to optimize the shell layer construction. The code for this study is available at https://***/abdullah1aloush1/MuGONA.

关键词： Pathfinding ordering algorithms Computational efficiency Distance cost Shell layers

来源：评论

学校读者我要写书评

暂无评论

On the impact of spatial covariance matrix ordering on tile low-rank estimation of Matérn parameters

引用

ENVIRONMETRICS 2024年第6期35卷

作者： Chen, Sihan Abdulah, Sameh Sun, Ying Genton, Marc G. King Abdullah Univ Sci & Technol Stat Program Thuwal 23955 Saudi Arabia King Abdullah Univ Sci & Technol Extreme Comp Res Ctr ECRC Thuwal Saudi Arabia

Spatial statistical modeling involves processing an nxn$$ n\times n $$ symmetric positive definite covariance matrix, where n$$ n $$ denotes the number of locations. However, when n$$ n $$ is large, processing this covariance matrix using traditional methods becomes prohibitive. Thus, coupling parallel processing with approximation can be an elegant solution by relying on parallel solvers that deal with the matrix as a set of small tiles instead of the full structure. The approximation can also be performed at the tile level for better compression and faster execution. The tile low-rank (TLR) approximation has recently been used to compress the covariance matrix, which mainly relies on ordering the matrix elements, which can impact the compression quality and the efficiency of the underlying solvers. This work investigates the accuracy and performance of location-based ordering algorithms. We highlight the pros and cons of each ordering algorithm and give practitioners hints on carefully choosing the ordering algorithm for TLR approximation. We assess the quality of the compression and the accuracy of the statistical parameter estimates of the Mat & eacute;rn covariance function using TLR approximation under various ordering algorithms and settings of correlations through simulations on irregular grids. Our conclusions are supported by an application to daily soil moisture data in the Mississippi Basin area.

关键词： covariance function Gaussian process ordering algorithms statistical modeling tile low-rank (TLR) approximation

来源：评论

学校读者我要写书评

暂无评论

Hybrid direct and iterative solver with library of multi-criteria optimal orderings for h adaptive finite element method computations

Hybrid direct and iterative solver with library of multi-cri...

引用

16th Annual International Conference on Computational Science (ICCS)

作者： AbouEisha, Hassan Jopek, Konrad Medygral, Bartlomiej Moshkov, Mikhail Nosek, Szymon Paszynska, Anna Paszynski, Maciej Pingali, Keshav King Abdullah Univ Sci & Technol Comp Sci Thuwal Saudi Arabia King Abdullah Univ Sci & Technol Appl Math & Computat Sci Thuwal Saudi Arabia AGH Univ Sci & Technol Dept Comp Sci Krakow Poland Jagiellonian Univ Fac Phys Astron & Appl Comp Sci Krakow Poland Univ Texas Austin Inst Computat & Engn Sci Austin TX 78712 USA

In this paper we present a multi-criteria optimization of element partition trees and resulting orderings for multi-frontal solver algorithms executed for two dimensional h adaptive finite element method. In particular, the problem of optimal ordering of elimination of rows in the sparse matrices resulting from adaptive finite element method computations is reduced to the problem of finding of optimal element partition trees. Given a two dimensional h refined mesh, we find all optimal element partition trees by using the dynamic programming approach. An element partition tree defines a prescribed order of elimination of degrees of freedom over the mesh. We utilize three different metrics to estimate the quality of the element partition tree. As the first criterion we consider the number of floating point operations(FLOPs) performed by the multi-frontal solver. As the second criterion we consider the number of memory transfers (MEMOPS) performed by the multi-frontal solver algorithm. As the third criterion we consider memory usage (NONZEROS) of the multi-frontal direct solver. We show the optimization results for FLOPs vs MEMOPS as well as for the execution time estimated as FLOPs+100*MEMOPS vs NONZEROS. We obtain Pareto fronts with multiple optimal trees, for each mesh, and for each refinement level. We generate a library of optimal elimination trees for small grids with local singularities. We also propose an algorithm that for a given large mesh with identified local sub-grids, each one with local singularity. We compute Schur complements over the sub-grids using the optimal trees from the library, and we submit the sequence of Schur complements into the iterative solver ILUPCG.

关键词： finite element method h adaptivity multi-frontal direct solver element partition tree ordering algorithms ILUPCG

来源：评论

学校读者我要写书评

暂无评论

Hybrid Direct and Iterative Solver with Library of Multi-criteria Optimal orderings for h Adaptive Finite Element Method Computations

引用

Procedia Computer Science 2016年 80卷 865-874页

作者： Hassan AbouEisha Konrad Jopek Bartłomiej Medygrał Mikhail Moshkov Szymon Nosek Anna Paszyńska Maciej Paszyński Keshav Pingali Computer Science King Abdullah University of Science and Technology Thuwal Saudi Arabia Department of Computer Science AGH University of Science and Technology Kraków Poland Applied Mathematics and Computational Science King Abdullah University of Science and Technology Thuwal Saudi Arabia Faculty of Physics Astronomy and Applied Computer Science Jagiellonian University Kraków Poland Institute for Computational and Engineering Sciences The University of Texas at Austin USA

关键词： finite element method h adaptivity multi-frontal direct solver element partition tree ordering algorithms ILUPCG

来源：评论

学校读者我要写书评

暂无评论

Benchmarking ordering techniques for nonserial dynamic programming

引用

MEMETIC COMPUTING 2012年第3期4卷 201-208页

作者： Sviridenko, Alexander Shcherbina, Oleg Tavrian Natl Univ Fac Math & Comp Sci Vernadsky Av 4 UA-95007 Simferopol Ukraine Univ Vienna Fac Math A-1090 Vienna Austria

Five ordering algorithms for the nonserial dynamic programming algorithm for solving sparse discrete optimization problems are compared in this paper. The benchmarking reveals that the ordering of the variables has a significant impact on the run-time of these algorithms. In addition, it is shown that different orderings are most effective for different classes of problems. Finally, it is shown that, amongst the algorithms considered here, heuristics based on maximum cardinality search and minimum fill-in perform best for solving the discrete optimization problems considered in this paper.

关键词： Discrete optimization Nonserial dynamic programming Benchmarking ordering algorithms

来源：评论

学校读者我要写书评

暂无评论

Numbering techniques for preconditioners in iterative solvers for compressible flows

引用

INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN FLUIDS 2007年第3期55卷 241-261页

作者： Pollul, B. Reusken, A. Univ Aachen Rhein Westfal TH Aachen Inst Geometri & Prakt Math D-52056 Aachen Germany

We consider Newton-Krylov methods for solving discretized compressible Euler equations. A good preconditioner in the Krylov subspace method is crucial for the efficiency of the solver. In this paper we consider a point-block Gauss-Seidel method as preconditioner. We describe and compare renumbering strategies that aim at improving the quality of this preconditioner. A variant of reordering methods known from multigrid for convection-dominated elliptic problems is introduced. This reordering algorithm is essentially black-box and significantly improves the robustness and efficiency of the point-block Gauss-Seidel preconditioner. Results of numerical experiments using the QUADFLOW solver and the PETSc library are given. Copyright (c) 2007 John Wiley & Sons, Ltd.

关键词： Euler equations Krylov subspace methods preconditioning ordering algorithms

来源：评论

学校读者我要写书评

暂无评论

Towards a tighter coupling of bottom-up and top-down sparse matrix ordering methods

引用

BIT NUMERICAL MATHEMATICS 2001年第4期41卷 800-841页

作者： Schulze, J Univ Gesamthsch Paderborn Dept Comp Sci D-33102 Paderborn Germany

Most state-of-the-art ordering schemes for sparse matrices are a hybrid of a bottom-up method such as minimum degree and a top-down scheme such as George's nested dissection. In this paper we present an ordering algorithm that achieves a tighter coupling of bottom-up and top-down methods. In our methodology vertex separators axe interpreted as the boundaries of the remaining elements in an unfinished bottom-up ordering. As a consequence, we are using bottom-up techniques such as quotient graphs and special node selection strategies for the construction of vertex separators. Once all separators have been found, we are using them as a skeleton for the computation of several bottom-up orderings. Experimental results show that the orderings obtained by our scheme are in general better than those obtained by other ordering codes.

关键词： ordering algorithms minimum degree algorithm nested dissection

来源：评论

学校读者我要写书评

暂无评论

Modeling and improving locality for the sparse-matrix-vector product on cache memories

引用

FUTURE GENERATION COMPUTER SYSTEMS 2001年第1期18卷 55-67页

作者： Heras, DB Blanco, V Cabaleiro, JC Rivera, FF Univ Santiago Compostela Dept Elect & Computac Santiago De Compostela 15706 Spain

A model for representing and improving the locality exhibited by the execution of sparse irregular problems is developed in this work. We focus on the product of a sparse matrix by a dense vector (SpM x V). We consider the cache memory as a representative level of the memory hierarchy. Locality is evaluated through four functions based on two parameters called entry matches and line matches. In order to increase the locality, two algorithms are applied: one based on the construction of minimum spanning trees and the other on the nearest-neighbor heuristic. These techniques were tested and compared with some standard ordering algorithms. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： sparse matrix memory hierarchy cache memory locality ordering algorithms

来源：评论

学校读者我要写书评

暂无评论

Genetic algorithm optimisation of a class of inventory control systems

引用

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS 2000年第3期68卷 259-278页

作者： Disney, SM Naim, MM Towill, DR Univ Wales Dept Maritime Studies & Int Transport Logist Syst Dynam Grp Cardiff CF1 3YP S Glam Wales

The paper describes a procedure for optimising the performance of an industrially designed inventory control system. This has the three classic control policies utilising sales, inventory and pipeline information to set the order rate so as to achieve a desired balance between capacity, demand and minimum associated stock level. A first step in optimisation is the selection of appropriate "benchmark" performance characteristics. Five are considered herein and include inventory recovery to "shock" demands;in-built filtering capability;robustness to production lead-time variations;robustness to pipeline level information fidelity;and systems selectivity. A genetic algorithm for optimising system performance, via these five vectors is described. The optimum design parameters are presented for various vector weightings. This leads to a decision support system for the correct setting of the system controls under various operating scenarios. The paper focuses on a single supply chain interface, however the methodology is also applicable to complete supply chains. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： inventory control optimisation simulation ordering algorithms

来源：评论

学校读者我要写书评

暂无评论

Robust ordering of sparse matrices using multisection

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 1998年第3期19卷 816-832页

作者： Ashcraft, C Liu, JWH Boeing Informat & Support Serv Seattle WA 98124 USA York Univ Dept Comp Sci N York ON M3J 1P3 Canada

In this paper we provide a robust reordering scheme for sparse matrices. The scheme relies on the notion of multisection, a generalization of bisection. The reordering strategy is demonstrated to have consistently good performance in terms of fill reduction when compared with multiple minimum degree and generalized nested dissection. Experimental results show that by using multisection, we obtain an ordering which is consistently as good as or better than both for a wide spectrum of sparse problems.

关键词： ordering algorithms minimum degree algorithm nested dissection

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：