aproximari de functii utilizand polinoame de grade foarte mari si aplicatii

Aproximari de functii utilizand polinoame de grade foarte mari si aplicatii

Aproximari de functii utilizand polinoame de grade foarte mari si aplicatiiSupervizor: Prof. Dr. Ing. Octavian CRET

Autor: Filip Silviu-IoanCuprinsJustificare si obiectivele proiectuluiSolutii existenteSolutia propusaImplementare si testareRezultate si concluzii

Justificare si obictivele proiectuluiTeoria aproximarilor numerice sta la baza calculelor din multe din domeniile de activitate curente (cercetari stiintifice, inginerie, finante, etc.)

Numerele utilizate sunt reprezentate in formate cu precizie limitata (virgula fixa, virgula mobila, etc.) aritmetici specializate pe aceste formate

Starea actualaJustificare si obictivele proiectuluiDorinta de a studia comportamentul metodelor existente de aproximare a functiilor numerice in vederea extinderii acestora in alte domenii, cum ar fi procesarea semnalelor digitaleOferirea unor metode de calcul numeric cat mai preciseMotivatiaCuprinsJustificare si obiectivele proiectuluiSolutii existenteSolutia propusaImplementare si testareRezultate si concluzii

Solutii existenteNumeroase rezultate teoretice si practice (dezvoltare Taylor, alg. Remez, etc.)Sunt usor de stocat in memoriePermit o evaluare eficienta prin utilizarea:Schemei lui HornerOperatiei de adunare inmultire fuzionate FMA

Q: Este chiar asa de usor?A: De fapt, NU.De ce polinoame?Solutii existenteAmintim:sistemele de calcul pot reprezenta doar un subset finit de numere reale, stocate de obicei in virgula mobila;Constrangerile hardware si de eficienta pot forta coeficientii aceluiasi polinom sa:Utilizeze formate diferiteSa aiba precizii diferiteSa aiba valori fixate trebuie luate in calcul spatiu finit de cautare al polinoamelorConstrangeri(1)Solutii existenteConstrangeri(2)CuprinsJustificare si obiectivele proiectuluiSolutii existenteSolutia propusaImplementare si testareRezultate si concluzii

Solutia propusaTine cont de toate constrangerile foloseste rezultate din teoria retelelor laticiale euclidiene

Se reduce la a rezolva o problema de tip CVP (Closest Vector Problem)Prezentare generalaSolutia propusa

Exemplu: Reteaua generata de vectorii (2, 1) si (0, 2)Solutia propusa

Exemplu: CVPSolutia propusa

Exemplu: CVPSolutia propusaProblema NP-dura algoritmi de rezolvare exponentiali, intractabili pentru dimensiuni mari utilizam algoritmi rapizi, mai imprecisiAlgoritmul lui Babai: porneste de la o retea generata de vectori foarte scurti problema SVP (Shortest Vector Problem) rezolvabila cu algoritmul LLL.Rezolvarea problemei CVPSolutia propusaArhitectura (fluxul de executie al aplicatiei)Generator puncte de interpolareModelator constrangeri coeficientiGenerator baza retea laticialaRezolvitor CVP (alg. Babai)Generator coeficienti polinom de aproximareFunctia de aproximatMapare interval de aproximare pe cercul trigonometric + determianare puncte egal distantate pe cercReducere problema la lucru cu intregi (se elimina erorile de rotunjire)Aplicare algoritm Babai (LLL)Rezolvare sistem de ecuatii liniare ce determina valorile coeficentilorCuprinsJustificare si obiectivele proiectuluiSolutii existenteSolutia propusaImplementare si testareRezultate si concluzii

Implementare si testareGenerator puncte de interpolareModelator constrangeri coeficientiGenerator baza retea laticialaTehnologii folosite (C/C++)Librariile GMP si MPFR pentru calcule cu numere intregi si in virgula mobila de precizie arbitrareRezolvitor CVP (alg. Babai)Libraria fplll ce contine implementari foarte rapide pentru algoritmii LLL si BabaiGenerator coeficienti polinom de aproximareLibrariile ATLAS si IML pentru rezolvare de sisteme liniare intregi de grad foarte mareImplementare si testareEvaluare si testareCuprinsJustificare si obiectivele proiectuluiSolutii existenteSolutia propusaImplementare si testareRezultate si concluzii

Rezultate si concluziiCalcularea certificata: utilitarul Sollya

Evolutia eroriiVa multumesc pentru atentie!Intrebari? Sugestii?