The Experts below are selected from a list of 81810 Experts worldwide ranked by ideXlab platform

Martin Vohralík - One of the best experts on this subject based on the ideXlab platform.

  • p-robust equilibrated flux reconstruction in H(curl) based on local minimizations. Application to a posteriori analysis of the curl-curl problem
    2021
    Co-Authors: Théophile Chaumont-frelet, Martin Vohralík
    Abstract:

    We present a local construction of H(curl)-conforming piecewise Polynomials satisfying a prescribed curl constraint. We start from a piecewise Polynomial not contained in the H(curl) space but satisfying a suitable orthogonality property. The procedure employs minimizations in vertex patches and the outcome is, up to a generic constant independent of the underlying Polynomial Degree, as accurate as the best-approximations over the entire local versions of H(curl). This allows to design guaranteed, fully computable, constant-free, and Polynomial-Degree-robust a posteriori error estimates of Prager-Synge type for Nédélec finite element approximations of the curl-curl problem. A divergence-free decomposition of a divergence-free H(div)-conforming piecewise Polynomial, relying on over-constrained minimizations in Raviart-Thomas spaces, is the key ingredient. Numerical results illustrate the theoretical developments.

  • Guaranteed and robust $L^2$-norm a posteriori error estimates for 1D linear advection problems
    ESAIM: Mathematical Modelling and Numerical Analysis, 2021
    Co-Authors: Alexandre Ern, Martin Vohralík, Mohammad Zakerzadeh
    Abstract:

    We propose a reconstruction-based a posteriori error estimate for linear advection problems in one space dimension. In our framework, a stable variational ultra-weak formulation is adopted, and the equivalence of the $L_2$-norm of the error with the dual graph norm of the residual is established. This dual norm is showed to be localizable over vertex-based patch subdomains of the computational domain under the condition of the orthogonality of the residual to the piecewise affine hat functions. We show that this condition is valid for some well-known numerical methods including continuous/discontinuous Petrov-Galerkin and discontinuous Galerkin methods. Consequently, a well-posed local problem on each patch is identified, which leads to a global conforming reconstruction of the discrete solution. We prove that this reconstruction provides a guaranteed upper bound on the $L_2$ error. Moreover, up to a constant, it also gives local lower bounds on the $L_2$ error, where the generic constant is proven to be independent of mesh-refinement, Polynomial Degree of the approximation, and the advective velocity. This leads to robustness of our estimates with respect to the advection as well as the Polynomial Degree. All the above properties are verified in a series of numerical experiments, additionally leading to asymptotic exactness. Motivated by these results, we finally propose a heuristic extension of our methodology to any space dimension, achieved by solving local least-squares problems on vertex-based patches. Though not anymore guaranteed, the resulting error indicator is numerically robust with respect to both advection velocity and Polynomial Degree, for a collection of two-dimensional test cases including discontinuous solutions.

  • stable broken h1 and h div Polynomial extensions for Polynomial Degree robust potential and flux reconstruction in three space dimensions
    IEEE Communications Magazine, 2019
    Co-Authors: Alexandre Ern, Martin Vohralík
    Abstract:

    We study extensions of piecewise Polynomial data prescribed on faces and possibly in elements of a patch of simplices sharing a vertex. In the H1 setting, we look for functions whose jumps across the faces are prescribed, whereas in the H(div) setting, the normal component jumps and the piecewise divergence are prescribed. We show stability in the sense that the minimizers over piecewise Polynomial spaces of the same Degree as the data are subordinate in the broken energy norm to the minimizers over the whole broken H and H(div) spaces. Our proofs are constructive and yield constants independent of the Polynomial Degree. One particular application of these results is in a posteriori error analysis, where the present results justify Polynomial-Degree-robust efficiency of potential and flux reconstructions.

  • Guaranteed and robust a posteriori bounds for Laplace eigenvalues and eigenvectors: a unified framework
    Numerische Mathematik, 2018
    Co-Authors: Eric Cancès, Geneviève Dusson, Yvon Maday, Benjamin Stamm, Martin Vohralík
    Abstract:

    This paper develops a general framework for a posteriori error estimates in numerical approximations of the Laplace eigenvalue problem, applicable to all standard numerical methods. Guaranteed and computable upper and lower bounds on an arbitrary simple eigenvalue are given, as well as on the energy error in the approximation of the associated eigenvector. The bounds are valid under the sole condition that the approximate i -th eigenvalue lies between the exact $$(i-1)$$ ( i - 1 ) -th and $$(i+1)$$ ( i + 1 ) -th eigenvalue, where the relative gaps are sufficiently large. We give a practical way how to check this; the accuracy of the resulting estimates depends on these relative gaps. Our bounds feature no unknown (solution-, regularity-, or Polynomial-Degree-dependent) constant, are optimally convergent (efficient), and Polynomial-Degree robust. Under a further explicit, a posteriori, minimal resolution condition, the multiplicative constant in our estimates can be reduced by a fixed factor; moreover, when an elliptic regularity assumption on the corresponding source problem is satisfied with known constants, this multiplicative constant can be brought to the optimal value of 1 with mesh refinement. Applications of our framework to nonconforming, discontinuous Galerkin, and mixed finite element approximations of arbitrary Polynomial Degree are provided, along with numerical illustrations. Our key ingredients are equivalences between the i -th eigenvalue error, the associated eigenvector energy error, and the dual norm of the residual. We extend them in an appendix to the generic class of bounded-below self-adjoint operators with compact resolvent.

  • Guaranteed and robust a posteriori bounds for Laplace eigenvalues and eigenvectors: a unified framework
    Numerische Mathematik, 2018
    Co-Authors: Eric Cancès, Geneviève Dusson, Yvon Maday, Benjamin Stamm, Martin Vohralík
    Abstract:

    This paper develops a general framework for a posteriori error estimates in numerical approximations of the Laplace eigenvalue problem, applicable to all standard numerical methods. Guaranteed and computable upper and lower bounds on an arbitrary simple eigenvalue are given, as well as on the energy error in the approximation of the associated eigenvector. The bounds are valid under the sole condition that the approximate i-th eigenvalue lies between the exact (i−1)-th and (i+1)-th eigenvalue, where the relative gaps are sufficiently large. We give a practical way how to check this; the precision of the resulting estimates depends on these relative gaps. Our bounds feature no unknown (solution-, regularity-, or Polynomial-Degree-dependent) constant, are optimally convergent (efficient), and Polynomial-Degree robust. Under a further explicit, a posteriori, minimal resolution condition, the multiplicative constant in our estimates can be reduced by a fixed factor; moreover, when an elliptic regularity assumption on the corresponding source problem is satisfied with known constants, this multiplicative constant can be brought to the optimal value of 1 with mesh refinement. Applications of our framework to nonconforming, discontinuous Galerkin, and mixed finite element approximations of arbitrary Polynomial Degree are provided, along with numerical illustrations. Our key ingredient are equivalences between the i-th eigenvalue error, the associated eigenvector energy error, and the dual norm of the residual. We extend them in an appendix to the generic class of bounded-below self-adjoint operators with compact resolvent.

Andris Ambainis - One of the best experts on this subject based on the ideXlab platform.

  • Polynomial Degree and lower bounds in quantum complexity collision and element distinctness with small range
    Theory of Computing, 2005
    Co-Authors: Andris Ambainis
    Abstract:

    We give a general method for proving quantum lower bounds for problems with small range. Namely, we show that, for any symmetric problem defined on functions f : {1,..., N} ! {1,..., M}, its Polynomial Degree is the same for all M N. Therefore, if we have a quantum query lower bound for some (possibly quite large) range M which is shown using the Polynomials method, we immediately get the same lower bound for all ranges M N. In particular, we get Ω(N 1/3 ) and Ω(N 2/3 ) quantum lower bounds for collision and element distinctness with small range, respectively. As a corollary, we obtain a better lower bound on the Polynomial Degree of the two-level AND-OR tree.

  • Polynomial Degree vs quantum query complexity
    Foundations of Computer Science, 2003
    Co-Authors: Andris Ambainis
    Abstract:

    The Degree of a Polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. We exhibit a function with Polynomial Degree M and quantum query complexity (M/sup 1.321.../). This is the first superlinear separation between Polynomial Degree and quantum query complexity. The lower bound is shown by a new, more general version of quantum adversary method.

  • Polynomial Degree and lower bounds in quantum complexity collision and element distinctness with small range
    arXiv: Quantum Physics, 2003
    Co-Authors: Andris Ambainis
    Abstract:

    We give a general method for proving quantum lower bounds for problems with small range. Namely, we show that, for any symmetric problem defined on functions $f:\{1, ..., N\}\to\{1, ..., M\}$, its Polynomial Degree is the same for all $M\geq N$. Therefore, if we have a quantum lower bound for some (possibly, quite large) range $M$ which is shown using Polynomials method, we immediately get the same lower bound for all ranges $M\geq N$. In particular, we get $\Omega(N^{1/3})$ and $\Omega(N^{2/3})$ quantum lower bounds for collision and element distinctness with small range.

  • Polynomial Degree vs quantum query complexity
    arXiv: Quantum Physics, 2003
    Co-Authors: Andris Ambainis
    Abstract:

    The Degree of a Polynomial representing (or approximating) a function f is a lower bound for the number of quantum queries needed to compute f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. We exhibit a function with Polynomial Degree M and quantum query complexity \Omega(M^{1.321...}). This is the first superlinear separation between Polynomial Degree and quantum query complexity. The lower bound is shown by a new, more general version of quantum adversary method.

He Yang - One of the best experts on this subject based on the ideXlab platform.

  • error estimates of runge kutta discontinuous galerkin methods for the vlasov maxwell system
    Mathematical Modelling and Numerical Analysis, 2015
    Co-Authors: He Yang
    Abstract:

    In this paper, error analysis is established for Runge–Kutta discontinuous Galerkin (RKDG) methods to solve the Vlasov–Maxwell system. This nonlinear hyperbolic system describes the time evolution of collisionless plasma particles of a single species under the self-consistent electromagnetic field, and it models many phenomena in both laboratory and astrophysical plasmas. The methods involve a third order TVD Runge–Kutta discretization in time and upwind discontinuous Galerkin discretizations of arbitrary order in phase domain. With the assumption that the exact solutions have sufficient regularity, the L 2 errors of the particle number density function as well as electric and magnetic fields at any given time T are bounded by C h k + 1 / 2 + C τ 3 under a CFL condition τ / h ≤ γ . Here k is the Polynomial Degree used in phase space discretization, satisfying (with d x being the dimension of spatial domain), τ is the time step, and h is the maximum mesh size in phase space. Both C and γ are positive constants independent of h and τ , and they may depend on the Polynomial Degree k , time T , the size of the phase domain, certain mesh parameters, and some Sobolev norms of the exact solution. The analysis can be extended to RKDG methods with other numerical fluxes and to RKDG methods solving relativistic Vlasov–Maxwell equations.

  • error estimates of runge kutta discontinuous galerkin methods for the vlasov maxwell system
    arXiv: Numerical Analysis, 2013
    Co-Authors: He Yang
    Abstract:

    In this paper, error analysis is established for Runge-Kutta discontinuous Galerkin (RKDG) methods to solve the Vlasov-Maxwell system. This nonlinear hyperbolic system describes the time evolution of collisionless plasma particles of a single species under the self-consistent electromagnetic field, and it models many phenomena in both laboratory and astrophysical plasmas. The methods involve a third order TVD Runge-Kutta discretization in time and upwind discontinuous Galerkin discretizations of arbitrary order in phase domain. With the assumption that the exact solution has sufficient regularity, the $L^2$ errors of the particle number density function as well as electric and magnetic fields at any given time $T$ are bounded by $C h^{k+\frac{1}{2}}+C\tau^3$ under a CFL condition $\tau /h \leq \gamma$. Here $k$ is the Polynomial Degree used in phase space discretization, satisfying $k \geq \left \lceil \frac{d_x + 1}{2} \right \rceil$ (the smallest integer greater than or equal to $\frac{d_x+1}{2}$, with $d_x$ being the dimension of spatial domain), $\tau$ is the time step, and $h$ is the maximum mesh size in phase space. Both $C$ and $\gamma$ are positive constants independent of $h$ and $\tau$, and they may depend on the Polynomial Degree $k$, time $T$, the size of the phase domain, certain mesh parameters, and some Sobolev norms of the exact solution. The analysis can be extended to RKDG methods with other numerical fluxes and to RKDG methods solving relativistic Vlasov-Maxwell equations.

Hartmut Klauck - One of the best experts on this subject based on the ideXlab platform.

  • the partition bound for classical communication complexity and query complexity
    Conference on Computational Complexity, 2010
    Co-Authors: Rahul Jain, Hartmut Klauck
    Abstract:

    We describe new lower bounds for randomized communication complexity and query complexity which we call the partition bounds. They are expressed as the optimum value of linear programs. For communication complexity we show that the partition bound is stronger than both the rectangle/corruption bound and the γ2/generalized discrepancy bounds. In the model of query complexity we show that the partition bound is stronger than the approximate Polynomial Degree and classical adversary bounds. We also exhibit an example where the partition bound is quadratically larger than the approximate Polynomial Degree and adversary bounds.

  • the partition bound for classical communication complexity and query complexity
    arXiv: Computational Complexity, 2009
    Co-Authors: Rahul Jain, Hartmut Klauck
    Abstract:

    We describe new lower bounds for randomized communication complexity and query complexity which we call the partition bounds. They are expressed as the optimum value of linear programs. For communication complexity we show that the partition bound is stronger than both the rectangle/corruption bound and the \gamma_2/generalized discrepancy bounds. In the model of query complexity we show that the partition bound is stronger than the approximate Polynomial Degree and classical adversary bounds. We also exhibit an example where the partition bound is quadratically larger than Polynomial Degree and classical adversary bounds.

Vohralík Martin - One of the best experts on this subject based on the ideXlab platform.

  • Guaranteed and robust $L^2$-norm a posteriori error estimates for 1D linear advection problems
    'EDP Sciences', 2021
    Co-Authors: Ern Alexandre, Vohralík Martin, Zakerzadeh Mohammad
    Abstract:

    International audienceWe propose a reconstruction-based a posteriori error estimate for linear advection problems in one space dimension. In our framework, a stable variational ultra-weak formulation is adopted, and the equivalence of the $L_2$-norm of the error with the dual graph norm of the residual is established. This dual norm is showed to be localizable over vertex-based patch subdomains of the computational domain under the condition of the orthogonality of the residual to the piecewise affine hat functions. We show that this condition is valid for some well-known numerical methods including continuous/discontinuous Petrov-Galerkin and discontinuous Galerkin methods. Consequently, a well-posed local problem on each patch is identified, which leads to a global conforming reconstruction of the discrete solution. We prove that this reconstruction provides a guaranteed upper bound on the $L_2$ error. Moreover, up to a constant, it also gives local lower bounds on the $L_2$ error, where the generic constant is proven to be independent of mesh-refinement, Polynomial Degree of the approximation, and the advective velocity. This leads to robustness of our estimates with respect to the advection as well as the Polynomial Degree. All the above properties are verified in a series of numerical experiments, additionally leading to asymptotic exactness. Motivated by these results, we finally propose a heuristic extension of our methodology to any space dimension, achieved by solving local least-squares problems on vertex-based patches. Though not anymore guaranteed, the resulting error indicator is numerically robust with respect to both advection velocity and Polynomial Degree, for a collection of two-dimensional test cases including discontinuous solutions

  • On the derivation of guaranteed and p-robust a posteriori error estimates for the Helmholtz equation
    Springer Verlag, 2021
    Co-Authors: Chaumont-frelet Théophile, Ern Alexandre, Vohralík Martin
    Abstract:

    International audienceWe propose a novel a posteriori error estimator for conforming finite element discretizations of two- and three-dimensional Helmholtz problems.The estimator is based on an equilibrated flux that is computed by solving patchwise mixed finite element problems. We show that the estimator is reliable up to a prefactor that tends to one with mesh refinement or with Polynomial Degree increase. We also derive a fully computable upper bound on the prefactor for several common settings of domains and boundary conditions. This leads to a guaranteed estimate without any assumption on the mesh size or the Polynomial Degree, though the obtained guaranteed bound may lead to large error overestimation. We next demonstrate that the estimator is locally efficient, robust in all regimes with respect to the Polynomial Degree, and asymptotically robust with respect to the wavenumber. Finally we present numerical experiments that illustrate our analysis and indicate that our theoretical results are sharp

  • Equivalence of local-and global-best approximations, a simple stable local commuting projector, and optimal $hp$ approximation estimates in $H$(div)
    'Oxford University Press (OUP)', 2021
    Co-Authors: Ern Alexandre, Gudi Thirupathi, Smears Iain, Vohralík Martin
    Abstract:

    International audienceGiven an arbitrary function in H(div), we show that the error attained by the global-best approximation by $H$(div)-conforming piecewise Polynomial Raviart-Thomas-Nédélec elements under additional constraints on the divergence and normal flux on the boundary, is, up to a generic constant, equivalent to the sum of independent local-best approximation errors over individual mesh elements, without constraints on the divergence or normal fluxes. The generic constant only depends on the shape-regularity of the underlying simplicial mesh, the space dimension, and the Polynomial Degree of the approximations. The analysis also gives rise to a stable, local, commuting projector in $H$(div), delivering an approximation error that is equivalent to the local-best approximation. We next present a variant of the equivalence result, where robustness of the constant with respect to the Polynomial Degree is attained for unbalanced approximations. These two results together further enable us to derive rates of convergence of global-best approximations that are fully optimal in both the mesh size $h$ and the Polynomial Degree $p$, for vector fields that only feature elementwise the minimal necessary Sobolev regularity. We finally show how to apply our findings to derive optimal a priori $hp$-error estimates for mixed and least-squares finite element methods applied to a model diffusion problem

  • Equivalence of local-and global-best approximations, a simple stable local commuting projector, and optimal hp approximation estimates in H(div)
    HAL CCSD, 2020
    Co-Authors: Ern Alexandre, Gudi Thirupathi, Smears Iain, Vohralík Martin
    Abstract:

    Given an arbitrary function in H(div), we show that the error attained by the global-best approximation by H(div)-conforming piecewise Polynomial Raviart-Thomas-Nédélec elements under additional constraints on the divergence and normal flux on the boundary, is, up to a generic constant, equivalent to the sum of independent local-best approximation errors over individual mesh elements, without constraints on the divergence or normal fluxes. The generic constant only depends on the shape-regularity of the underlying simplicial mesh, the space dimension, and the Polynomial Degree of the approximations. The analysis also gives rise to a stable, local, commuting projector in H(div), delivering an approximation error that is equivalent to the local-best approximation. We next present a variant of the equivalence result, where robustness of the constant with respect to the Polynomial Degree is attained for unbalanced approximations. These two results together further enable us to derive rates of convergence of global-best approximations that are fully optimal in both the mesh size h and the Polynomial Degree p, for vector fields that only feature elementwise the minimal necessary Sobolev regularity. We finally show how to apply our findings to derive optimal a priori hp-error estimates for mixed and least-squares finite element methods applied to a model diffusion problem

  • Equivalence of local-and global-best approximations, a simple stable local commuting projector, and optimal $hp$ approximation estimates in $H(\mathrm{div})$
    2020
    Co-Authors: Ern Alexandre, Gudi Thirupathi, Smears Iain, Vohralík Martin
    Abstract:

    Given an arbitrary function in H(div), we show that the error attained by the global-best approximation by H(div)-conforming piecewise Polynomial Raviart-Thomas-N\'ed\'elec elements under additional constraints on the divergence and normal flux on the boundary, is, up to a generic constant, equivalent to the sum of independent local-best approximation errors over individual mesh elements, without constraints on the divergence or normal fluxes. The generic constant only depends on the shape-regularity of the underlying simplicial mesh, the space dimension, and the Polynomial Degree of the approximations. The analysis also gives rise to a stable, local, commuting projector in H(div), delivering an approximation error that is equivalent to the local-best approximation. We next present a variant of the equivalence result, where robustness of the constant with respect to the Polynomial Degree is attained for unbalanced approximations. These two results together further enable us to derive rates of convergence of global-best approximations that are fully optimal in both the mesh size h and the Polynomial Degree p, for vector fields that only feature elementwise the minimal necessary Sobolev regularity. We finally show how to apply our findings to derive optimal a priori hp-error estimates for mixed and least-squares finite element methods applied to a model diffusion problem