The book contains the methods and bases of functional analysis that are directly adjacent to the problems of numericalmathematics and its applications; they are what one needs for the understand ing from a gene...
详细信息
ISBN:
(数字)9781461241287
ISBN:
(纸本)9780817638887;9781461286660
The book contains the methods and bases of functional analysis that are directly adjacent to the problems of numericalmathematics and its applications; they are what one needs for the understand ing from a general viewpoint of ideas and methods of computationalmathematics and of optimization problems for numerical algorithms. Functional analysis in mathematics is now just the small visible part of the iceberg. Its relief and summit were formed under the influence of this author's personal experience and tastes. This edition in English contains some additions and changes as compared to the second edition in Russian; discovered errors and misprints had been corrected again here; to the author's distress, they jump incomprehensibly from one edition to another as fleas. The list of literature is far from being complete; just a number of textbooks and monographs published in Russian have been included. The author is grateful to S. Gerasimova for her help and patience in the complex process of typing the mathematical manuscript while the author corrected, rearranged, supplemented, simplified, general ized, and improved as it seemed to him the book's contents. The author thanks G. Kontarev for the difficult job of translation and V. Klyachin for the excellent figures.
A metric graph is a pair (G, d), where G is a graph and d: E(G) -> R->= 0 is a distance function. Let p is an element of [1, infinity] be fixed. An isometric embedding of the metric graph (G, d) in l(p)(k) = (R-...
详细信息
A metric graph is a pair (G, d), where G is a graph and d: E(G) -> R->= 0 is a distance function. Let p is an element of [1, infinity] be fixed. An isometric embedding of the metric graph (G, d) in l(p)(k) = (R-k, d(p)) is a map phi : V(G) -> R-k such that d(p)(phi(v), phi(w)) = d(vw) for all edges vw is an element of E(G). The l(p)-dimension of G is the least integer k such that there exists an isometric embedding of (G, d) in l(p)(k) for all distance functions d such that (G, d) has an isometric embedding in l(p)(K) for some K. It is easy to show that l(p)-dimension is a minor-monotone property. In this paper, we characterize the minor-closed graph classes C with bounded l(p)-dimension, for p is an element of {2, infinity}. For p = 2, we give a simple proof that C has bounded l(2)-dimension if and only if C has bounded treewidth. In this sense, the l(2)-dimension of a graph is 'tied' to its treewidth. For p = infinity, the situation is completely different. Our main result states that a minor-closed class C has bounded l(infinity)-dimension if and only if C excludes a graph obtained by joining copies of K-4 using the 2-sum operation, or excludes a Mobius ladder with one 'horizontal edge' removed.
The main purpose of this paper is to develop a new method based on operational matrices of the linear cardinal B-spline (LCB-S) functions to numerically solve of the fractional stochastic integro-differential (FSI-D) ...
详细信息
The main purpose of this paper is to develop a new method based on operational matrices of the linear cardinal B-spline (LCB-S) functions to numerically solve of the fractional stochastic integro-differential (FSI-D) equations. To reach this aim, LCB-S functions are introduced and their properties are considered, briefly. Then, the operational matrices based on LCB-S functions are constructed, for the first time, including the fractional Riemann-Liouville integral operational matrix, the stochastic integral operational matrix, and the integer integral operational matrix. The main characteristic of the new scheme is to convert the FSI-D equation into a linear system of algebraic equations which can be easily solved by applying a suitable method. Also, the convergence analysis and error estimate of the proposed method are studied and an upper bound of error is obtained. numerical experiments are provided to show the potential and efficiency of the new method. Finally, some numerical results, for various values of perturbation in the parameters of the main problem are presented which can indicate the stability of the suggested method.
作者：
Natale, AndreaTodeschi, GabrieleUniv Lille
Lab Paul Painleve CNRS Project Team RapsodiInriaUMR 8524 F-59000 Lille France PSL Res Univ
Univ Paris Dauphine Project Team Mokaplan INRIAUMR CNRS 7534Ceremade Paris France
In this paper we introduce a new class of finite element discretizations of the quadratic optimal transport problem based on its dynamical formulation. These generalize to the finite element setting the finite differe...
详细信息
In this paper we introduce a new class of finite element discretizations of the quadratic optimal transport problem based on its dynamical formulation. These generalize to the finite element setting the finite difference scheme proposed by Papadakis et al. (SIAM J Imaging Sci, 7(1): 212-238,2014). We solve the discrete problem using a proximal splitting approach and we show how to modify this in the presence of regularization terms which are relevant for physical data interpolation.
Let L be a set of n lines in the plane, not necessarily in general position. We present an efficient algorithm for finding all the vertices of the arrangement A(L) of maximum level, where the level of a vertex v is th...
详细信息
Let L be a set of n lines in the plane, not necessarily in general position. We present an efficient algorithm for finding all the vertices of the arrangement A(L) of maximum level, where the level of a vertex v is the number of lines of L that pass strictly below v. The problem, posed in Exercise 8.13 in de Berg et al. (computational Geometry. Algorithms and Applications. Springer, Berlin (2008)), appears to be much harder than it seems at first sight, as this vertex might not be on the upper envelope of the lines. We first assume that all the lines of L are distinct, and distinguish between two cases, depending on whether or not the upper envelope of L contains a bounded edge. In the former case, we show that the number of lines of L that pass above any maximum level vertex v(0) is only O (log n). In the latter case, we establish a similar property that holds after we remove some of the lines that are incident to the single vertex of the upper envelope. We present algorithms that run, in both cases, in optimal O (n log n) time. We then consider the case where the lines of L are not necessarily distinct. This setup is more challenging, and for this case we present an algorithm that computes all the maximum-level vertices in time O(n(4/3) log(3) n). Finally, we consider a related combinatorial question for degenerate arrangements, where many lines may intersect in a single point, but all the lines are distinct: We bound the complexity of the weighted k-level in such an arrangement, where the weight of a vertex is the number of lines that pass through the vertex. We show that the bound in this case is O(n(4/3)), which matches the corresponding bound for non-degenerate arrangements, and we use this bound in the analysis of one of our algorithms.
We study the complexity of geometric problems on spaces of low fractal dimension. It was recently shown in Sidiropoulos and Sridhar (33rd International Symposium on computational Geometry (Brisbane 2017). Leibniz Int....
详细信息
We study the complexity of geometric problems on spaces of low fractal dimension. It was recently shown in Sidiropoulos and Sridhar (33rd International Symposium on computational Geometry (Brisbane 2017). Leibniz Int. Proc. Inform., vol. 77, # 58. Leibniz-Zent. Inform., Wadern, 2017) that several problems admit improved solutions when the input is a pointset in Euclidean space with fractal dimension smaller than the ambient dimension. In this paper we prove nearly-matching lower bounds, thus establishing nearly-optimal bounds for various problems as a function of the fractal dimension. More specifically, we show that for any integer d > 1, any delta is an element of (1, d), and any n is an element of N, there exists a set X of n points in R-d, with fractal dimension delta such that for any epsilon > 0 and c >= 1, any c-spanner of X has treewidth Omega(n(1-1/(delta-epsilon))/c(d-1)). This lower bound matches the previous upper bound. The construction used to prove this lower bound on the treewidth of spanners, can also be used to derive lower bounds on the running time of algorithms for various problems, assuming the Exponential Time Hypothesis. We provide two prototypical results of this type: - For any delta is an element of(1, d) and any epsilon > 0, d-dimensional Euclidean TSP on n points with fractal dimension atmost delta cannot be solved in time 2(O(n1-1/(delta-epsilon))). The best-known upper bound is 2(O(n1-1/delta log n)). - For any delta is an element of(1, d) and any epsilon > 0, the problem of finding k-pairwise non-intersecting d-dimensional unit balls/axis-parallel unit cubes with centers having fractal dimension at most delta cannot be solved in time f (k) n(O(k1-1/(delta-epsilon))) for any computable function f. The best-known upper bound is n(O(k1-1/delta log n)). The above results nearly match previously known upper bounds from [op. cit.], and generalize analogous lower bounds for the case of ambient dimension due to Marx and Sidiropoulos (30th Ann
For fixed k we prove exponential lower bounds on the equilateral number of subspaces of l(infinity)(n) of codimension k. In particular, we showthat subspaces of codimension 2 of l(infinity)(n+2) and subspaces of codim...
详细信息
For fixed k we prove exponential lower bounds on the equilateral number of subspaces of l(infinity)(n) of codimension k. In particular, we showthat subspaces of codimension 2 of l(infinity)(n+2) and subspaces of codimension 3 of l(infinity)(n+3) 8 have an equilateral set of cardinality n + 1 if n >= 7 and n >= 12 respectively. Moreover, the same is true for every normed space of dimension n, whose unit ball is a centrally symmetric polytope with at most 4n/3 - o(n) pairs of facets.
Shellings of simplicial complexes have long been a useful tool in topological and algebraic combinatorics. Shellings of a complex expose a large amount of information in a helpful way, but are not easy to construct, o...
详细信息
Shellings of simplicial complexes have long been a useful tool in topological and algebraic combinatorics. Shellings of a complex expose a large amount of information in a helpful way, but are not easy to construct, often requiring deep information about the structure of the complex. It is natural to ask whether shellings may be efficiently found computationally. In a recent paper, Goaoc, Patak, Patakova, Tancer, and Wagner gave a negative answer to this question (assuming P not equal NP), showing that the problem of deciding whether a simplicial complex is shellable is NP-complete. In this paper, we give simplified constructions of various gadgets used in the NP-completeness proof of these authors. Using these gadgets combined with relative shellability and other ideas, we also exhibit a simpler proof of the NP-completeness of the shellability decision problem. Our method systematically uses relative shellings to build up large shellable complexes with desired properties.
暂无评论