Michael Griebel, Peter Oswald
We present convergence results in expectation for stochastic subspace correction schemes and their accelerated versions to solve symmetric positive-definite variational problems, and discuss their potential for achieving fault tolerance in an unreliable compute network. We employ the standard overlapping domain decomposition algorithm for PDE discretizations to discuss the latter aspect.
Michael Griebel, Peter Oswald
We consider an incremental approximation method for solving variational problems in infinite-dimensional Hilbert spaces, where in each step a randomly and independently selected subproblem from an infinite collection of subproblems is solved. we show that convergence rates for the expectation of the squared error can be guaranteed under weaker conditions than previously established in [Constr. Approx. 44:1 (2016), 121-139]. A connection to the theory of learning algorithms in reproducing kernel Hilbert spaces is revealed.
Peter Oswald
We show that the d-dimensional Haar system H^d on the unit cube I^d is a Schauder basis in the classical Besov space B_{p,q,1}^s(I^d), 0<p<1, defined by first order differences in the limiting case s=d(1/p-1), if and only if 0<q\le p. For d=1 and p<q, this settles the only open case in our 1979 paper [4], where the Schauder basis property of H in B_{p,q,1}^s(I) for 0<p<1 was left undecided. We also consider the Schauder basis property of H^d for the standard Besov spaces B_{p,q}^s(I^d) defined by Fourier-analytic methods in the limiting cases s=d(1/p-1) and s=1, complementing results by Triebel [7].
Peter Oswald
Compared to conforming P1 finite elements, nonconforming P1 finite element discretizations are thought to be less sensitive to the appearance of distorted triangulations. E.g., optimal-order discrete $H^1$ norm best approximation error estimates for $H^2$ functions hold for arbitrary triangulations. However, similar estimates for the error of the Galerkin projection for second-order elliptic problems show a dependence on the maximum angle of all triangles in the triangulation. We demonstrate on the example of a special family of distorted triangulations that this dependence is essential, and due to the deterioration of the consistency error. We also provide examples of sequences of triangulations such that the nonconforming P1 Galerkin projections for a Poisson problem with polynomial solution do not converge or converge at arbitrarily slow speed. The results complement analogous findings for conforming P1 elements.
Peter Oswald
We reconsider some estimates the paper "M. Griebel, P. Oswald, On additive Schwarz preconditioners for sparse grid discretizations. Numer. Math. 66 (1994), 449-463" concerning the hierarchical basis preconditioner for sparse grid discretizations. The improvement is in three directions: We consider arbitrary space dimensions d>1, give bounds for generalized sparse grid spaces with arbitrary monotone index set, and show that the bounds are sharp up to constants depending only on d, at least for a subclass of generalized sparse grid spaces containing full grid, standard sparse grid spaces, and energy-norm optimized sparse grid spaces.
Peter Oswald, Weiqi Zhou
When iteratively solving linear systems By=b with Hermitian positive semi-definite $B$, and in particular when solving least-squares problems for $Ax=b$ by reformulating them as $AA^\ast y=b$, it is often observed that SOR-type methods (Gauss-Seidel, Kaczmarz) perform suboptimally for the given equation ordering, and that random reordering improves the situation on average.This paper is an attempt to provide some additional theoretical support for this phenomenon. We show eerror bounds for two randomized versions, called shuffled and preshuffled SOR, that improve asymptotically upon the best known bounds fro SOR with cyclic ordering. Our results are based on studying the behavior of the triangular truncation of Hermitian matrices with respect to their permutations.
Michael Griebel, Peter Oswald
We present an approach to defining Hilbert spaces of functions depending on infinitely many variables or parameters, with emphasis on a weighted tensor product construction based on stable space splittings, The construction has been used in an exemplary way for guiding dimension- and scale-adaptive algorithms in application areas such as statistical learning theory, reduced order modeling, and information-based complexity. We prove results on compact embeddings, norm equivalences, and the estimation of $epsilon$-dimensions. A new condition for the equivalence of weighted ANOVA and anchored norms is also given.
Michael Griebel, Peter Oswald
We prove the convergence of greedy and randomized versions of Schwarz iterative methods for solving linear elliptic variational problems based on infinite space splittings of a Hilbert space. For the greedy case, we show a squared error decay rate of $O((m+1)^{-1})$ for elements of an approximation space $\mathcal{A}_1$ related to the underlying splitting. For the randomized case, we show an expected squared error decay rate of $O((m+1)^{-1})$ on a class $\mathcal{A}_{\infty}^π\subset \mathcal{A}_1$ depending on the probability distribution.
Peter Oswald, Tatiana Shingel
The problem of finding the correct asymptotic rate of approximation by polynomial loops in dependence of the smoothness of the elements of a loop group seems not well-understood in general. For matrix Lie groups such as SU(N), it can be viewed as a problem of nonlinearly constrained trigonometric approximation. Motivated by applications to optical FIR filter design and control, we present some initial results for the case of SU(N)-loops, N>1. In particular, using representations via the exponential map and ideas from splitting methods, we prove that the best approximation of an SU(N)-loop belonging to a Hoelder-Zygmund class Lip_alpha with alpha>1/2 by a polynomial SU(N)-loop of degree n is of the order O(n^{-α/(1+α)}) as n tends to infinity. Although this approximation rate is not considered final (and can be improved in special cases), to our knowledge it is the first general, nontrivial result of this type.
Peter Oswald
For the L_2-orthogonal projector P onto spaces of linear splines over simplicial partitions of polyhedral domains in R^d, d>1, we show that the L_infty norm of P cannot be bounded uniformly with respect to the partition. This is in contrast to d=1, where these norms are bounded by 3 independently of the partition. This negative result is folklore among specialists in finite element methods and approximation theory but seemingly has never been formally proved.