Computation in Nonlinear Filtering

非线性滤波中的计算

• 批准号: 9975354
• 负责人: Stephen S. Yau
• 金额: $ 15.5万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-07-15 至 2002-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9975354&HistoricalAwards=false
• 关键词: Computation; Nonlinear; Filtering

9973247We suggest problems in computational and applied linear algebra that come under three headings. (i) Under the first heading come two problems on parallel computations. The first concerns a divide and conquer approach to the problem of computing the mean first passage matrix for Markov chains, work that was started in the case when the process is a random walk with an underlying cutpoint graph structure, e.g., a tree. The second problem is to investigate the speed-up due to the addition of processors, when the number of blocks (natural partitions) is kept fixed, in a model of asynchronous iterations. One factor here is the type of coefficient matrix to which the model is applied. (ii) Under the second heading comes a problem encountered when working onconvergence of infinite products of matrices. It is known that in iterative methods for computing a solution to singular systems, e.g., in computing the stationary distribution for a Markov process, the magnitude of the subdominant eigenvalue determines the asymptotic rate of convergence. We have noticed that for random stochastic matrices the subdominant eigenvalue seems to decay exactly as the square root of n. We suggest investigating this behavior. (iii) Here we suggest two problems on approximating the algebraic connectivity of a graph which is the second smallest eigenvalue of its Laplacian matrix. Estimates of this quantity are used in various graph-based algorithms such as the spectral separator method. In the first problem we suggest investigating bounds derived from the generalized group inverse of the Laplacian which seems to yield good lower bounds. In the second problem we propose studying the algebraic connectivity of random graphs on n vertices. Throughout the proposal we give examples from the literature for the applications of the problems set forth.Because many practical problems are very intricate, we need to build models to represent them and then develop a way of understanding and handling the models. Such modeling frequently results in large arrays of numbers or, what is often associated with the arrays, a system with many equations and many unknowns. The numbers in the array can be of a random nature if the model represents a physical situation (scientific, economic, social or statistical) in which there is some randomness involved. If the model represents a more deterministic physical situation, there will be definite numbers with some relations between them. Once we have a model, there may be many parameters and features which we need to measure and compute. This proposal suggests seven problems. Two of the problems concern certain high-performance computing with these models. The computations are to be performed in parallel so as to achieve speed-up of the computation and, if possible, a reduction in the number of computations. Two examples of questions are: If a problem partitions naturally into a number of subproblems which are called blocks, and if we begin to increase beyond the number of blocks, the number of computers/processors applied to solve in parallel the entire problem, do we necessarily continue to increase the speed of calculations, or is a point of saturation reached after a while and what do we do then? A common situation in which such a problem arises is in data-fitting, sometimes known as the least-squares problem. Another problem for computation in parallel is in physical systems which have states with a probability of going from one state to another. An example is various types of population concentrations such as urban, suburban, rural, etc. with a probability of moving from one type of region to another. We may be interested in the distribution of the population in the different conurbations after a short term. It turns out that such predictions may be done in parallel under certain underlying assumptions.

9973247我们建议在计算和应用线性代数中的问题分为三个标题。(I)第一个标题下有两个有关并行计算的问题。第一种是关于计算马尔可夫链的平均首次通过矩阵问题的分而治之的方法，该工作是在过程是具有底层割点图结构(例如树)的随机游动的情况下开始的。第二个问题是研究在异步迭代模型中，当块(自然分区)的数量保持不变时，由于添加处理器而导致的加速。这里的一个因素是应用该模型的系数矩阵的类型。(Ii)在第二个标题下是在研究矩阵的无穷乘积的收敛时遇到的问题。众所周知，在计算奇异系统解的迭代方法中，例如在计算马尔可夫过程的平稳分布时，次优特征值的大小决定了收敛的渐近速度。我们已经注意到，对于随机随机矩阵，次优势特征值似乎完全按照n的平方根衰减。我们建议研究这一行为。(Iii)在这里，我们提出了两个关于逼近图的代数连通性的问题，该图是它的拉普拉斯矩阵的第二小特征值。对这个量的估计被用于各种基于图形的算法，例如谱分离方法。在第一个问题中，我们建议研究从拉普拉斯的广义群逆导出的界，这似乎产生了良好的下界。在第二个问题中，我们建议研究n个顶点上的随机图的代数连通性。在整个提案中，我们从文献中给出了应用问题集的例子。由于许多实际问题非常复杂，我们需要建立模型来表示它们，然后开发一种理解和处理模型的方法。这样的建模经常会产生大的数字数组，或者，通常与数组相关联的是具有许多方程和许多未知数的系统。如果模型代表的物理情况(科学、经济、社会或统计)中包含一些随机性，则数组中的数字可以是随机的。如果模型代表了一个更具确定性的物理情况，就会有一些确定的数字，它们之间存在一定的关系。一旦我们有了模型，可能会有许多参数和特征需要我们测量和计算。这项提议提出了七个问题。其中两个问题与这些模型的某些高性能计算有关。这些计算将并行执行，以实现计算的加速，并在可能的情况下减少计算的数量。两个问题的例子是：如果一个问题自然地分成许多子问题，称为块，如果我们开始增加到超过块的数量，即应用于并行解决整个问题的计算机/处理器的数量，我们是否一定要继续提高计算速度，或者在一段时间后达到饱和点，然后我们怎么办？出现这种问题的一种常见情况是数据拟合，有时称为最小二乘问题。并行计算的另一个问题是在物理系统中，这些系统的状态有可能从一种状态转移到另一种状态。一个例子是各种类型的人口集中，如城市、郊区、农村等，有可能从一种类型的区域转移到另一种类型的区域。我们可能会对短期后不同城市的人口分布感兴趣。事实证明，在某些潜在的假设下，这些预测可能是并行进行的。