Computation in Nonlinear Filtering

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

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.