The approximate inverse in action III: 3D-Doppler tomography

Summary. The approximate inverse is a powerful tool for solving first kind operator equations in a stable way. Its abstract convergence and stability theory developed in our articles [SIAM J. Numer. Anal., 37, 1909-1929,2000] and [Math. Comp., 72, 1399-1415, 2003] is applied to the reconstruction problem of 3D-vector field tomography resulting in a reconstruction algorithm of filtered backprojection type. For an analytically computed reconstruction filter (reconstruction kernel) convergence with rates as well as the regularization property are established.Mathematics Subject Classification (1991): 65J10, 65R10The work was partially supported by a Feodor Lynen-Fellowship of the Alexander von Humboldt-Foundation.Correspondence to: A. Rieder     

Retrieving random media

Benjamini asked whether the scenery reconstruction methods of Matzinger (see e.g. [21], [22], [20]) can be done in polynomial time. In this article, we give the following answer for a 2-color scenery and simple random walk with holding: We prove that a piece of the scenery of length of the order 3 ⁿ around the origin can be reconstructed – up to a reflection and a small translation – with high probability from the first 2 · 3^{10 αn} observations with a constant α > 0 independent of n. Thus, the number of observations needed is polynomial in the length of the piece of scenery which we reconstruct. The probability that the reconstruction fails tends to 0 as n→∞. In contrast to [21], [22], and [20], the proofs in this article are all constructive. Our reconstruction algorithm is an algorithm in the sense of computer science. This is the first article which shows that the scenery reconstruction is also possible in the 2-color case with holding. The case with holding is much more difficult than [22] and requires completely different methods.     

2.5维介质Born近似波速反演唯一性

考虑脉冲源引起的２．５维弱不均匀介质波速反演问题，利用线性化方法得到了波速的二维小扰动满足的积分方程，这是一个积分几何的问题，进而由Ｆｏｕｒｉｅｒ变换和脉冲函数的性质将此二维积分方程化为单变量的积分方程，最后用压缩映象理论证明了积分方程解的唯一性。本文给出了二给波速反演的一种新算法。同时，唯一性结果证明了已有的迭代算法的合理性。     

An algorithm for reconstructing convex bodies from their projections

An algorithm is described for the approximative reconstruction of a plane convex body from its projections in a finite number of directions.A priori anda posteriori error estimates are given, and the convergence of certain sequences of an approximative solution of the reconstruction problem to the exact solution is proven. Finally, it is shown that, after small modifications, the algorithm can be applied to reconstruct convex bodies from discrete projectional data.The algorithm consists in an approximation of the convex body, to be reconstructed, by recursively defined cores and envelopes, following the ideas of Kuba [6] for the reconstruction of binary patterns.This paper was started at the University of Erlangen-Nürnberg in 1983–1984, when the second author was a fellow of the Alexander von Humboldt Foundation, while the last author was supported by the German Research Council (DFG, Contract Ko-506/8-1).     

Schensted Algorithms for Dual Graded Graphs

This paper is a sequel to [3]. We keep the notation and terminology and extend the numbering of sections, propositions, and formulae of [3].The main result of this paper is a generalization of the Robinson-Schensted correspondence to the class of dual graded graphs introduced in [3], This class extends the class of Y-graphs, or differential posets [22], for which a generalized Schensted correspondence was constructed earlier in [2].The main construction leads to unified bijective proofs of various identities related to path counting, including those obtained in [3]. It is also applied to permutation enumeration, including rook placements on Ferrers boards and enumeration of involutions.As particular cases of the general construction, we re-derive the classical algorithm of Robinson, Schensted, and Knuth [19, 12], the Sagan-Stanley [18], Sagan-Worley [16, 29] and Haiman's [11] algorithms and the author's algorithm for the Young-Fibonacci graph [2]. Some new applications are suggested.The rim hook correspondence of Stanton and White [23] and Viennot's bijection [28] are also special cases of the general construction of this paper.In [5], the results of this paper and the previous paper [3] were presented in a form of extended abstract.     

Convergence of the point vortex method for the 3-D euler equations

We prove consistency, stability, and convergence of a point vortex approximation to the 3-D incompressible Euler equations with smooth solutions. The 3-D algorithm we consider here is similar to the corresponding 3-D vortex blob algorithm introduced by Beale and Majda; see [3]. We first show that the discretization error is second-order accurate. Then we show that the method is stable in l^p norm for the particle trajectories and in w^?1.p norm for discrete vorticity. Consequently, the method converges up to any time for which the Euler equations have a smooth solution. One immediate application of our convergence result is that the vortex filament method without smoothing also converges.     

分布式系统上并行矩阵乘法

1．引言矩阵乘法是最简单的数学问题,同时由于其计算量大而通常被用来对计算机的浮点运算速度进行测试,尤其是对于并行计算机,其并行效率的好坏可通过这个简单的问题反应出来,如果在这个问题上都不能取得很好的效果,对于其它问题就更不可能．此外,为了提高计算性能,对求解数值代数中的问题最终会归结到有矩阵乘法的计算,如LAPACK,ScaLAPACK等,因此有效地并行计算矩阵乘法在实际应用中是非常重要的．矩阵乘法是做C＝A×B,其中A是m×k阵,B是k×n阵,C是m×n阵．设矩阵A,B可以分成p×p块矩阵,即A＝（Ai,j）p×p,B＝（B…     

有限元解三维弹性波方程的并行算法

研究弹性固体中波的传播问题由来已久,由于地震学、石油勘探、地震层析成像等方面的重要应用,三维弹性波方程的求解问题在工业应用中显得日益重要.自七十年代末由石油勘探界首先引入有限元方法求解二维弹性波方程以来,这一公认精度较高的方法在求解三维弹性波方程方面研究成果尚不多见,其主要原因是该问题需要较大的计算机存贮量和计算量.对三维问题使用一般的有限元方法求解,常常需要几十万次反复递推求解高达10~7阶以上的大型线性代数方程组.对于这类超大型的计算课题,目前的     

A modified bisection algorithm for the determination of the eigenvalues of a symmetric tridiagonal matrix

Summary A modification to the well known bisection algorithm [1] when used to determine the eigenvalues of a real symmetric matrix is presented. In the new strategy the terms in the Sturm sequence are computed only as long as relevant information on the required eigenvalues is obtained. The resulting algorithm usingincomplete Sturm sequences can be shown to minimise the computational work required especially when only a few eigenvalues are required.The technique is also applicable to other computational methods which use the bisection process.     

Inversion of general tridiagonal matrices

In the current work, the authors present a symbolic algorithm for finding the inverse of any general nonsingular tridiagonal matrix. The algorithm is mainly based on the work presented in [Y. Huang, W.F. McColl, Analytic inversion of general tridiagonal matrices, J. Phys. A 30 (1997) 7919–7933] and [M.E.A. El-Mikkawy, A fast algorithm for evaluating nth order tridiagonal determinants, J. Comput. Appl. Math. 166 (2004) 581–584]. It removes all cases where the numeric algorithm in [Y. Huang, W.F. McColl, Analytic inversion of general tridiagonal matrices, J. Phys. A 30 (1997) 7919–7933] fails. The symbolic algorithm is suited for implementation using Computer Algebra Systems (CAS) such as MACSYMA, MAPLE and MATHEMATICA. An illustrative example is given.     

Pivoting strategy for rank-one modification ofLDM t-like factorization

The rank-one modification algorithm of theLDM ^t factorization was given by Bennett [1]. His method, however, could break down even when the matrix is nonsingular and well-conditioned. We introduce a pivoting strategy for avoiding possible break-down as well as for suppressing error growth in the modification process. The method is based on a symbolic formula of the rank-one modification of the factorization of a possibly singular nonsymmetric matrix. A new symbolic formula is also obtained for the inverses of the factor matrices. Repeated application of our method produces theLDM ^t-like product form factorization of a matrix. A numerical example is given to illustrate our pivoting method. An incomplete factorization algorithm is also introduced for updating positive definite matrix useful in quasi-Newton methods, in which the Fletcher and Powell algorithm [2] and the Gill, Murray and Saunders algorithm [4] are usually used.This paper is presented at the Japan SIAM Annual Meeting held at University of Tokyo, Japan, October 7–9, 1991.     

Rosen's Gradient Projection with discrete steps

In 1960, J. B. Rosen gave a famous Gradient Projection Method in [1]. But the convergence of the algorithm has not been proved for a long time. Many authors paid much attention to this problem, such as X.S. Zhang proved in [2] (1984) that the limit point of {x _k} which is generated by Rosen's algorithm is a K-T piont for a 3-dimensional caes, if {x _k} is convergent. D. Z. Du proved in [3] (1986) that Rosen's algorithm is convergent for 4-dimensional. In [4] (1986), the author of this paper gave a general proof of the convergence of Rosen's Gradient Projection Method for ann-dimensional case. As Rosen's method requires exact line search, we know that exact line search is very difficult on computer. In this paper a line search method of discrete steps are presented and the convergence of the algorithm is proved.     

Minimizing symmetric submodular functions

We describe a purely combinatorial algorithm which, given a submodular set functionf on a finite setV, finds a nontrivial subsetA ofV minimizingf[A] + f[V A]. This algorithm, an extension of the Nagamochi—Ibaraki minimum cut algorithm as simplified by Stoer and Wagner [M. Stoer, F. Wagner, A simple min cut algorithm, Proceedings of the European Symposium on Algorithms ESA '94, LNCS 855, Springer, Berlin, 1994, pp. 141–147] and by Frank [A. Frank, On the edge-connectivity algorithm of Nagamochi and Ibaraki, Laboratoire Artémis, IMAG, Université J. Fourier, Grenbole, 1994], minimizes any symmetric submodular function using O(|V|³) calls to a function value oracle. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.A preliminary version of this paper was presented at the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) in January 1995. This research was supported by the Natural Sciences and Engineering Research Council (NSERC) of Canada.     

Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups

A pseudo-natural algorithm for the word problem of a finitely presented group is an algorithm which not only tells us whether or not a word w equals 1 in the group but also gives a derivation of 1 from w when w equals 1. In [13], [14] Madlener and Otto show that, if we measure complexity of a primitive recursive algorithm by its level in the Grzegorczyk hierarchy, there are groups in which a pseudo-natural algorithm is arbitrarily more complicated than an algorithm which simply solves the word problem. In a given group the lowest degree of complexity that can be realised by a pseudo-natural algorithm is essentially the derivational complexity of that group. Thus the result separates the derivational complexity of the word problem of a finitely presented group from its intrinsic complexity. The proof given in [13] involves the construction of a finitely presented group G from a Turing machine T such that the intrinsic complexity of the word problem for G reflects the complexity of the halting problem of T, while the derivational complexity of the word problem for G reflects the runtime complexity of T. The proof of one of the crucial lemmas in [13] is only sketched, and part of the purpose of this paper is to give the full details of this proof. We will also obtain a variant of their proof, using modular machines rather than Turing machines. As for several other results, this simplifies the proofs considerably. MSC: 03D40, 20F10.     

Duality of Graded Graphs

A graph is said to be graded if its vertices are divided into levels numbered by integers, so that the endpoints of any edge lie on consecutive levels. Discrete modular lattices and rooted trees are among the typical examples. The following three types of problems are of interest to us:(1) path counting in graded graphs, and related combinatorial identities;(2) bijective proofs of these identities;(3) design and analysis of algorithms establishing corresponding bijections.This article is devoted to (1); its sequel [7] is concerned with the problems (2)–(3). A simplified treatment of some of these results can be found in [8].In this article, R.P. Stanley's [26, 27] linear-algebraic approach to (1) is extended to cover a wide range of graded graphs. The main idea is to consider pairs of graded graphs with a common set of vertices and common rank function. Such graphs are said to be dual if the associated linear operators satisfy a certain commutation relation (e.g., the Heisenberg one). The algebraic consequences of these relations are then interpreted as combinatorial identities. (This idea is also implicit in [27].)[7] contains applications to various examples of graded graphs, including the Young, Fibonacci, Young-Fibonacci and Pascal lattices, the graph of shifted shapes, the r-nary trees, the Schensted graph, the lattice of finite binary trees, etc. Many enumerative identities (both known and unknown) are obtained. Abstract of [7]. These identities can also be derived in a purely combinatorial way by generalizing the Robinson-Schensted correspondence to the class of graphs under consideration (cf. [5]). The same tools can be applied to permutation enumeration, including involution counting and rook polynomials for Ferrers boards. The bijective correspondences mentioned above are naturally constructed by Schensted-type algorithms. A general approach to these constructions is given. As particular cases we rederive the classical algorithm of Robinson, Schensted, and Knuth [20, 12, 21], the Sagan-Worley [17, 32] and Haiman [11] algorithms, the algorithm for the Young-Fibonacci graph [5, 15], and others. Several new applications are given.     

Computing a centerpoint of a finite planar set of points in linear time

The notion of a centerpoint of a finite set of points in two and higher dimensions is a generalization of the concept of the median of a set of reals. In this paper we present a linear-time algorithm for computing a centerpoint of a set ofn points in the plane, which is optimal compared with theO(n log³ n) complexity of the previously best-known algorithm. We use suitable modifications of the hamsandwich cut algorithm in [Me2] and the prune-and-search technique of Megiddo [Me1] to achieve this improvement.     

A perturbation result for bounded imaginary powers

We give a new proof of a perturbation result due to J. Prüss and H. Sohr [11]: if an operator A has bounded imaginary powers, then so does A+w (w ≧ 0). Instead of Mellin transform on which the proof in [11] is based, we use the functional calculus for sectorial operators developed in particular by A. McIntosh ([8], [3] and [1]). It turns out that our method gives a more general result than the one used in [11].     

L ∞ stability of the MUSCL methods

We present a general L ^∞ stability result for generic finite volume methods coupled with a large class of reconstruction for hyperbolic scalar equations. We show that the stability is obtained if the reconstruction respects two fundamental properties: the convexity property and the sign inversion property. We also introduce a new MUSCL technique named the multislope MUSCL technique based on the approximations of the directional derivatives in contrast to the classical piecewise reconstruction, the so-called monoslope MUSCL technique, based on the gradient reconstruction. We show that under specific constraints we shall detail, the two MUSCL reconstructions satisfy the convexity and sign inversion properties and we prove the L ^∞ stability.     

Shannon sampling II: Connections to learning theory

We continue our study [S. Smale, D.X. Zhou, Shannon sampling and function reconstruction from point values, Bull. Amer. Math. Soc. 41 (2004) 279–305] of Shannon sampling and function reconstruction. In this paper, the error analysis is improved. Then we show how our approach can be applied to learning theory: a functional analysis framework is presented; dimension independent probability estimates are given not only for the error in the L² spaces, but also for the error in the reproducing kernel Hilbert space where the learning algorithm is performed. Covering number arguments are replaced by estimates of integral operators.     

An efficient algorithm for the evacuation problem in a certain class of networks with uniform path-lengths

In this paper, we consider the evacuation problem in a network which consists of a directed graph with capacities and transit times on its arcs. This problem can be solved by the algorithm of Hoppe and Tardos [B. Hoppe, É. Tardos, The quickest transshipment problem, Math. Oper. Res. 25(1) (2000) 36–62] in polynomial time. However their running time is high-order polynomial, and hence is not practical in general. Thus, it is necessary to devise a faster algorithm for a tractable and practically useful subclass of this problem. In this paper, we consider a network with a sink s such that (i) for each vertex v≠s the sum of the transit times of arcs on any path from v to s takes the same value, and (ii) for each vertex v≠s the minimum v-s cut is determined by the arcs incident to s whose tails are reachable from v. This class of networks is a generalization of grid networks studied in the paper [N. Kamiyama, N. Katoh, A. Takizawa, An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity, IEICE Trans. Infrom. Syst. E89-D (8) (2006) 2372–2379]. We propose an efficient algorithm for this network problem.