turkmath.org

Türkiye'deki Matematiksel Etkinlikler


24 Eylül 2021, 17:00


İstanbul Matematiksel Bilimler Merkezi Seminerleri

Using Real Quantifier Elimination for Synthesizing Optimal Numerical Algorithms

Madalina Erascu
West University of Timisoara, Romanya

Various problems in mathematics, science and engineering can be reduced to real quantifier elimination (quantifier elimination over real closed fields). Around 1930, Alfred Tarski showed that real quantifier elimination can be carried out algorithmically. In 1975, George Collins provided a dramatically more efficient algorithm. Since then, there has been intensive research to make further improvement of efficiency for a certain important class of formulas (inputs). In our research, we consider formulas arising in the synthesis of optimal numerical algorithms. In this talk, we present a case study on the square root problem: given the real number x and the error bound eps, find a real interval such that it contains sqrt(x) and its width is less than eps. As usual, we begin by fixing an algorithm schema, namely, iterative refining: the algorithm starts with an initial interval and repeatedly updates it by applying a refinement function, say R on it until it becomes narrow enough. Then the synthesis amounts to finding a refinement function R that ensures that the algorithm is correct (loop invariant), terminating (contraction), and optimal. All these can be formulated as quantifier elimination over the real numbers. Hence, in principle, they can be all carried out automatically. However the computational requirement is so huge, making the automatic synthesis practically impossible with the current general quantifier elimination software. Hence, we did some hand derivations and were able to synthesize semi-automatically optimal algorithms under suitable assumptions.

This is joint work with Hoon Hong.


NOT: The meetings take place in IMBM (http://www.imbm.org.tr), but we plan to broadcast in zoom as well. To receive the zoom link, for this talk and future talks, you should register in the form https://tinyurl.com/symbolicmeetings

Uygulamalı Matematik İngilizce
IMBM and Zoom
İlgili Web Bağlantısı

admin 23.09.2021

Yaklaşan Seminerler Seminer Arşivi
 

İLETİŞİM

Akademik biriminizin ya da çalışma grubunuzun ülkemizde gerçekleşen etkinliklerini, ilan etmek istediğiniz burs, ödül, akademik iş imkanlarını veya konuk ettiğiniz matematikçileri basit bir veri girişi ile kolayca turkmath.org sitesinde ücretsiz duyurabilirsiniz. Sisteme giriş yapmak için gerekli bilgileri almak ya da görüş ve önerilerinizi bildirmek için iletişime geçmekten çekinmeyiniz. Katkı verenler listesi için tıklayınız.

Özkan Değer ozkandeger@gmail.com

DESTEK VERENLER

ja2019

31. Journees Arithmetiques Konferansı Organizasyon Komitesi

Web sitesinin masraflarının karşılanması ve hizmetine devam edebilmesi için siz de bağış yapmak, sponsor olmak veya reklam vermek için lütfen iletişime geçiniz.

ONLİNE ZİYARETÇİLER


©2013-2020 turkmath.org
Tüm hakları saklıdır