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

dynamic node adaptive strategy for nearly singular problems on large domains

ENGINEERING ANALYSIS WITH BOUNDARY ELEMENTS 2012年第9期36卷 1311-1321页

作者： Esmaeilbeigi, M. Hosseini, M. M. Yazd Univ Fac Math Yazd Iran

Many physical phenomena develop singular or nearly singular behavior in localized regions, e.g. boundary layers or blowup solutions. Using uniform grids for such problems becomes computationally prohibitive as the solution approaches singularity. For these problems, adaptive methods may be preferred over uniform grids methods. In large computational domains, because of the ill conditioning due to the large domain of the partial differential equation (PDE) problem, the existing node adaptive strategies perhaps encounter difficulty in detecting nearly singular regions. In this paper, we are interested in solving PDE problems on large domains, whose solution presents rapid variations or high gradients in some local regions of the domain. Our main purpose is to introduce a dynamic algorithm which finds regions with rapid variations and performs a local node adaptive strategy only in these nearly singular regions. In this algorithm, a step by step scheme is applied by using collocation points and thin plate spline radial basis functions. In spite of using local node adaptive strategy, the global solution exists in the whole computational domain. Another advantage of the new algorithm is its ability to keep the condition number and the required memory under control. The new algorithm is applied for two problems in two dimensions and the obtained results confirm the accuracy and efficiency of the proposed method. (C) 2012 Elsevier Ltd. All rights reserved.

关键词： RBF collocation dynamic algorithm Partial differential equations Thin plate splines Nearly singular problem Node adaptive

来源：评论

学校读者我要写书评

暂无评论

A dynamic density-based clustering method based on K-nearest neighbor

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2024年第5期66卷 3005-3031页

作者： Sorkhi, Mahshid Asghari Akbari, Ebrahim Rabbani, Mohsen Motameni, Homayun Islamic Azad Univ Dept Comp Engn Sari Branch Sari Iran Islamic Azad Univ Dept Appl Math Sari Branch Sari Iran

Many density-based clustering algorithms already proposed in the literature are capable of finding clusters with different shapes, sizes, and densities. Also, the noise points are detected well. However, many of these methods require input parameters that are static and must be defined by user. Since it is difficult for users to determine these parameters in large data sets, the proper determination of them has an effective role in the identification of a suitable clustering. Therefore, a challenge in this domain is how to reduce the number of input parameters, thereby reducing the errors caused by users' involvement. In order to handle this challenge, a dynamic density-based clustering (DDBC) method is proposed in this paper for clustering purposes, which needs the smallest number of parameters to be set by users since many of them are determined automatically. This method has the ability to distinguish close clusters with different densities in a dynamic manner. Additionally, it can detect outliers and noises before starting the clustering process without scanning these points. Several real and artificial data sets were used to examine the efficiency of the proposed method, and its outcomes were compared to those of other algorithms in this domain . The comparative results confirmed the acceptable performance of DDBC and its higher accuracy in clustering tasks.

关键词： Density-based clustering Outlier dynamic algorithm Nearest neighbors DBSCAN

来源：评论

学校读者我要写书评

暂无评论

dynamic EXPRESSION-TREES

引用

algorithmICA 1995年第3期13卷 245-265页

作者： COHEN, RF TAMASSIA, R Department of Computer Science Brown University Providence USA

We present a technique for dynamically maintaining a collection of arithmetic expressions represented by binary trees (whose leaves are variables and whose internal nodes are operators). A query operation asks for the value of an expression (associated with the root of a tree). Update operations include changing the value of a variable and combining or decomposing expressions by linking or cutting the corresponding trees. Our dynamic data structure uses linear space and supports queries and updates in logarithmic time. An important application is the dynamic maintenance of maximum flow and shortest path in series-parallel digraphs under a sequence of vertex and edge insertions, series and parallel compositions, and their respective inverses. Queries include reporting the maximum flow or shortest st-path in a series-parallel subgraph.

关键词： dynamic algorithm EXPRESSION EVALUATION SERIES-PARALLEL DIGRAPH

来源：评论

学校读者我要写书评

暂无评论

A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps

引用

SIAM JOURNAL ON COMPUTING 1996年第1期25卷 207-233页

作者： Chiang, YJ Preparata, FP Tamassia, R Department of Computer Science Brown University

We describe a new technique for dynamically maintaining the trapezoidal decomposition of a connected planar map M with n vertices and apply it to the development of a unified dynamic data structure that supports point-location, ray-shooting, and shortest-path queries in M. The space requirement is O(n log n). Point-location queries take time O(log n). Ray-shooting and shortest-path queries Lake time O(log(3) n) (plus O(k) time if the k edges of the shortest path are reported in addition to its length). Updates consist of insertions and deletions of vertices and edges, and take O(log(3) n) time (amortized for vertex updates). This is the first polylog-time dynamic data structure for shortest-path and ray-shooting queries. It is also the first dynamic point-location data structure for connected planar maps that achieves optimal query time.

关键词： point location ray shooting shortest path computational geometry dynamic algorithm

来源：评论

学校读者我要写书评

暂无评论

Partially dynamic efficient algorithms for distributed shortest paths

引用

THEORETICAL COMPUTER SCIENCE 2010年第7-9期411卷 1013-1037页

作者： Cicerone, Serafino D'Angelo, Gianlorenzo Di Stefano, Gabriele Frigioni, Daniele Univ Aquila Dipartimento Ingn Elettr & Informaz I-67040 Laquila Italy

We study the dynamic version of the distributed all-pairs shortest paths problem. Most of the solutions given in the literature for this problem, either (i) work under the assumption that before dealing with an edge operation, the algorithm for the previous operation has to be terminated, that is, they are not able to update shortest paths concurrently, or (ii) concurrently update shortest paths. but their convergence can be very slow (possibly infinite) due to the looping and counting infinity phenomena. In this paper, we propose partially dynamic algorithms that are able to concurrently update shortest paths. We experimentally analyze the effectiveness and efficiency of our algorithms by comparing them against several implementations of the well-known Bellman-Ford algorithm. (C) 2009 Elsevier B.V. All rights reserved.

关键词： dynamic algorithm Distributed algorithm Shortest paths

来源：评论

学校读者我要写书评

暂无评论

Improved algorithms for dynamic shortest paths

引用

algorithmICA 2000年第4期28卷 367-389页

作者： Djidjev, HN Pantziou, GE Zaroliagis, CD Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England Comp Technol Inst GR-26110 Patras Greece Kings Coll London Dept Comp Sci London WC2R 2LS England Rice Univ Dept Comp Sci Houston TX 77251 USA Max Planck Inst Informat Saarbrucken Germany

We describe algorithms for finding shortest paths and distances in outerplanar and planar digraphs that exploit the particular topology of the input graph. An important feature of our algorithms is that they can work in a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. In the case of outerplanar digraphs, our data structures can be updated after any such change in only logarithmic time. A distance query is also answered in logarithmic time. In the case of planar digraphs, we give an interesting tradeoff between preprocessing, query, and update times depending on the value of a certain topological parameter of the graph. Our results can be extended to n-vertex digraphs of genus O(n(1-epsilon)) for any epsilon > 0.

关键词： shortest path dynamic algorithm planar digraph outerplanar digraph

来源：评论

学校读者我要写书评

暂无评论

Partially dynamic maintenance of minimum weight hyperpaths

引用

JOURNAL OF DISCRETE algorithmS 2005年第1期3卷 27-46页

作者： Ausiello, Giorgio Franciosa, Paolo Giulio Frigioni, Daniele Univ Roma La Sapienza Dipartimento Informat Sistemist Via Salaria 113 I-00198 I- Roma Italy Univ Roma La Sapienza Dipartimento Stat Probabilita Stat Applicate I-00185 Rome Italy Univ Aquila Dipartimento Ingn Elettr I-67040 LAquila Italy

We address the problem of dynamically maintaining minimum weight hyperpaths in a directed hypergraph in a decremental setting. For such a problem, we provide a new efficient algorithm that works for a wide class of hyperpath weight measures. This algorithm explicitly updates minimum weight hyperpaths in O(L center dot C + max{n, C} center dot size(H)) worst case time under a sequence of L hyperarc weight increments and hyperarc deletions, where C is the maximum weight of minimum hyperpaths in H and size(H) is the size of the representation of the hypergraph. Hyperpath weight measures are only required to belong to the class of strict weakly superior functions. (C) 2004 Elsevier B.V. All rights reserved.

关键词： Directed hypergraph Minimum weight hyperpath dynamic algorithm

来源：评论

学校读者我要写书评

暂无评论

dynamic Matrix Rank with Partial Lookahead

引用

THEORY OF COMPUTING SYSTEMS 2014年第1期55卷 229-249页

作者： Kavitha, Telikepalli Tata Inst Fundamental Res Bombay 400005 Maharashtra India

We consider the problem of maintaining information about the rank of a matrix M under changes to its entries. For an nxn matrix M, we show an amortized upper bound of O(n (omega-1)) arithmetic operations per change for this problem, where omega < 2.373 is the exponent for matrix multiplication, under the assumption that there is a lookahead of up to I similar to(n) locations. That is, we know up to the next I similar to(n) locations (i (1),j (1)),(i (2),j (2)),aEuro broken vertical bar aEuro parts per thousand, whose entries are going to change, in advance;however we do not know the new entries in these locations in advance. We get the new entries in these locations in a dynamic manner. The dynamic matrix rank problem was first studied by Frandsen and Frandsen who showed an upper bound of O(n (1.575)) and a lower bound of Omega(n) for this problem and later Sankowski showed an upper bound of O(n (1.495)) for this problem when allowing randomization and a small probability of error. These algorithms do not assume any lookahead. For the dynamic matrix rank problem with lookahead, Sankowski and Mucha showed a randomized algorithm (with a small probability of error) that is more efficient than these algorithms.

关键词： dynamic algorithm Matrix rank Lookahead Bulk update using matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

A new dynamic approach for statistical optimization of GNSS radio occultation bending angles for optimal climate monitoring utility

引用

JOURNAL OF GEOPHYSICAL RESEARCH-ATMOSPHERES 2013年第23期118卷 13022-13040页

作者： Li, Y. Kirchengast, G. Scherllin-Pirscher, B. Wu, S. Schwaerz, M. Fritzer, J. Zhang, S. Carter, B. A. Zhang, K. RMIT Univ Satellite Positioning Atmosphere Climate & Enviro Melbourne Vic Australia Graz Univ Wegener Ctr Climate & Global Change WEGC Graz Austria Graz Univ IGAM IP Graz Austria

Global Navigation Satellite System (GNSS)-based radio occultation (RO) is a satellite remote sensing technique providing accurate profiles of the Earth's atmosphere for weather and climate applications. Above about 30km altitude, however, statistical optimization is a critical process for initializing the RO bending angles in order to optimize the climate monitoring utility of the retrieved atmospheric profiles. Here we introduce an advanced dynamic statistical optimization algorithm, which uses bending angles from multiple days of European Centre for Medium-range Weather Forecasts (ECMWF) short-range forecast and analysis fields, together with averaged-observed bending angles, to obtain background profiles and associated error covariance matrices with geographically varying background uncertainty estimates on a daily updated basis. The new algorithm is evaluated against the existing Wegener Center Occultation Processing System version 5.4 (OPSv5.4) algorithm, using several days of simulated MetOp and observed CHAMP and COSMIC data, for January and July conditions. We find the following for the new method's performance compared to OPSv5.4: 1.) it significantly reduces random errors (standard deviations), down to about half their size, and leaves less or about equal residual systematic errors (biases) in the optimized bending angles;2.) the dynamic (daily) estimate of the background error correlation matrix alone already improves the optimized bending angles;3.) the subsequently retrieved refractivity profiles and atmospheric (temperature) profiles benefit by improved error characteristics, especially above about 30km. Based on these encouraging results, we work to employ similar dynamic error covariance estimation also for the observed bending angles and to apply the method to full months and subsequently to entire climate data records.

关键词： GNSS Radio Occultation Statistical Optimization dynamic algorithm

来源：评论

学校读者我要写书评

暂无评论

An experimental study of dynamic algorithms for transitive closure

引用

ACM Journal of Experimental algorithmics 2001年 6卷 9–es页

作者： Frigioni, Daniele Miller, Tobias Nanni, Umberto Zaroliagis, Christos Dipartimento di Ingegneria Elettrica Universita dell'Aquila Monteluco di Roio 1-67040 L'Aquila Italy Transport- Informatik- und Logistik-Consulting GmbH Frankfurt Germany Dipartimento di Informatica e Sistemistica Universita di Roma la Sapienza 00198 Rome Via Salaria 113 Italy Computer Technology Institute University of Patras Department of Computer Engineering and Informatics 26500 Patras Greece

We have performed an extensive experimental study of several dynamic algorithms for transitive closure. In particular, we have implemented algorithms given by Italiano, Yellin, Cicerone et al., and two recent randomized algorithms by Henzinger and King. We propose a fine-tuned version of Italiano's algorithms as well as a new variant of them, both of which were always faster than any of the other implementations of the dynamic algorithms. We also considered simple-minded algorithms that were easy to implement and likely to be fast in practice. We tested and compared the above implementations on random inputs, on non-random inputs that are worst-case inputs for the dynamic algorithms, and on an input motivated by a real-world graph.

关键词： dynamic algorithm Experimentation Transitive Closure

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：