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 fo...
详细信息
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.
Flight delays (such as early or late arrivals and late departures) are a frequent occurrence in actual day to day airport operations and it is often not possible to assign such flights to their original gates. Flight ...
详细信息
Flight delays (such as early or late arrivals and late departures) are a frequent occurrence in actual day to day airport operations and it is often not possible to assign such flights to their original gates. Flight delay information may also vary with time. As a consequence, the airport authority needs to reassign flights to different gates in real-time. The traditional manual flight reassignment method is neither efficient nor effective in cases with variable flight delay information, and the reassignment is frequently time constrained. Consequently, in this study the goal is to develop a gate reassignment framework, and a systematic computerized tool, for repeatedly handling gate reassignments given varied flight delay information. The results of a test case related to Taiwan international airport operations, show that the proposed framework performs well.
A 3-D dynamic path-planning algorithm based on interfered fluid flow (DA) is proposed for unmanned aerial vehicle (UAV) in dynamic *** paper first describes the mathematical modeling of convex *** the static algorithm...
详细信息
ISBN:
(纸本)9781479946983
A 3-D dynamic path-planning algorithm based on interfered fluid flow (DA) is proposed for unmanned aerial vehicle (UAV) in dynamic *** paper first describes the mathematical modeling of convex *** the static algorithm based on interfered fluid flow (SA) is introduced and improved,whose planning path conforms to the general characteristic of phenomenon that running water can avoid rock and arrive at *** updating the information of obstacles and obtaining the relative velocity,we then transform the dynamic problem to static ***,DA is simplified by adopting ***,this dynamic algorithm proves to be efficient for real-time path planning by simulation results.
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 abou...
详细信息
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.
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 sol...
详细信息
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.
Given a multi-dimensional dataset of tuples, skyline computation returns a subset of tuples that are not dominated by any other tuples when all dimensions are considered together. Conventional skyline computation, how...
详细信息
Given a multi-dimensional dataset of tuples, skyline computation returns a subset of tuples that are not dominated by any other tuples when all dimensions are considered together. Conventional skyline computation, however, is inadequate to answer various queries that need to analyze not just individual tuples of a dataset but also their combinations. In this paper, we study group skyline computation which is based on the notion of dominance relation between groups of the same number of tuples. It determines the dominance relation between two groups by comparing their aggregate values such as sums or averages of elements of individual dimensions, and identifies a set of skyline groups that are not dominated by any other groups. We investigate properties of group skyline computation and develop a group skyline algorithm Gdynamic which is equivalent to a dynamic algorithm that fills a table of skyline groups. Experimental results show that Gdynamic is a practical group skyline algorithm. (C) 2011 Elsevier Inc. All rights reserved.
In this paper, a dynamic theorem proving (DTP) algorithm is proposed for dynamically judging whether a component set is consistency-based diagnosis in model-based diagnosis. Firstly, the model of the system to be diag...
详细信息
In this paper, a dynamic theorem proving (DTP) algorithm is proposed for dynamically judging whether a component set is consistency-based diagnosis in model-based diagnosis. Firstly, the model of the system to be diagnosed and all the observations are described with conjunctive normal forms (CNF), and the problem of diagnosis is translated into the satisfiability of the related clauses in the CNF files. Next. all the minimal consistency-based diagnostic sets are derived by calling DTP dynamically combining with the CSSE-tree. As the theorem about the number of components in minimal diagnosis is proposed, the majority of the non-minimal diagnosis can never be produced. Moreover, this approach can compute all the consistency-based diagnostic sets directly, without computing all the conflict sets and therefore the hitting sets of the collection of the corresponding conflict sets like the classical methods. Finally, the approach's soundness, completeness and complexity are analyzed and proved, and results show that the program is easy to be implemented, and the diagnosis efficiency is highly improved. (C) 2011 Elsevier Ltd. All rights reserved.
Spanner of an undirected graph G = (V, E) is a subgraph that is sparse and yet preserves all-pairs distances approximately. More formally, a spanner with stretch t is an element of N is a subgraph (V, E-S), E-S subset...
详细信息
Spanner of an undirected graph G = (V, E) is a subgraph that is sparse and yet preserves all-pairs distances approximately. More formally, a spanner with stretch t is an element of N is a subgraph (V, E-S), E-S subset of E such that the distance between any two vertices in the subgraph is at most t times their distance in G. Though G is trivially a t-spanner of itself, the research as well as applications of spanners invariably deal with a t-spanner that has as small number of edges as possible. We present fully dynamic algorithms for maintaining spanners in centralized as well as synchronized distributed environments. These algorithms are designed for undirected unweighted graphs and use randomization in a crucial manner. Our algorithms significantly improve the existing fully dynamic algorithms for graph spanners. The expected size (number of edges) of a t-spanner maintained at each stage by our algorithms matches, up to a polylogarithmic factor, the worst case optimal size of a t-spanner. The expected amortized time (or messages communicated in distributed environment) to process a single insertion/deletion of an edge by our algorithms is close to optimal.
We present the first fully dynamic algorithm for computing the characteristic polynomial of a matrix. In the generic symmetric case, our algorithm supports rank-one updates in O(n(2) log n) randomized time and queries...
详细信息
We present the first fully dynamic algorithm for computing the characteristic polynomial of a matrix. In the generic symmetric case, our algorithm supports rank-one updates in O(n(2) log n) randomized time and queries in constant time, whereas in the general case the algorithm works in O(n(2)k log n) randomized time, where k is the number of invariant factors of the matrix. The algorithm is based on the first dynamic algorithm for computing normal forms of a matrix such as the Frobenius normal form or the tridiagonal symmetric form. The algorithm can be extended to solve the matrix eigenproblem with relative error 2(-b) in additional O(n log(2) n log b) time. Furthermore, it can be used to dynamically maintain the singular value decomposition (SVD) of a generic matrix. Together with the algorithm, the hardness of the problem is studied. For the symmetric case, we present an Omega(n(2)) lower bound for rank-one updates and an Omega(n) lower bound for element updates. (C) 2010 Elsevier B.V. All rights reserved.
暂无评论