BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Florent Bréhard (Uppsala University\, Sweden) DTSTART:20210223T150000Z DTEND:20210223T160000Z DTSTAMP:20260423T024624Z UID:CRM-CAMP/32 DESCRIPTION:Title: Beyond Exponential Complexity of Newton-Galerkin Validation Methods: A P olynomial-Time Newton-Picard Validation Algorithm for linear ODEs\nby Florent Bréhard (Uppsala University\, Sweden) as part of CRM CAMP (Comput er-Assisted Mathematical Proofs) in Nonlinear Analysis\n\n\nAbstract\nA wi de range of techniques have been developed to compute validated numerical solutions to various kind of equations (e.g.\, ODE\, PDE\, DDE) arising in computer-assisted proofs. Among them are Newton-Galerkin a posteriori val idation techniques\, which provide error bounds for approximate solutions by using the contraction map principle in a suitable coefficient space (e. g.\, Fourier or Chebyshev). More precisely\, a contracting Newton-like ope rator is constructed by truncating and inverting the inverse Jacobian of t he equation.\nWhile these techniques were extensively used in cutting-edge works in the community\, we show that they suffer from an exponential run ning time w.r.t. the input equation. We illustrate this shortcomings on si mple linear ODEs\, where a "large" parameter in the equation leads to an i ntractable instance for Newton-Galerkin validation algorithms.\nFrom this observation\, we build a new validation scheme\, called Newton-Picard\, wh ich breaks this complexity barrier. The key idea consists in replacing the inverse Jacobian not by a finite-dimensional truncated matrix as in Newto n-Galerkin\, but by an integral operator with a polynomial approximation o f the so-called resolvent kernel. Moreover\, this method is also less basi s-dependent and more suitable to be formalized in a computer proof assista nt towards a fully certified implementation in the future.\n LOCATION:https://researchseminars.org/talk/CRM-CAMP/32/ END:VEVENT END:VCALENDAR