Numerical Analysis Research Group - Seminars 2016/17


Institute of Computer Science
ul. Joliot-Curie 15, Wrocław

Room 237 (Room 104, on special occasions)
Tuesdays, 14.15-16.00

30.05.2017
Bolesław Kacewicz (Akademia Górniczo-Hutnicza)
        Adaptacja i jej potencjalne przewagi w obliczeniach numerycznych
[Adaption and its potential advantages in numerical computation]

Streszczenie

We shall discuss advantages of adaptive information and adaptive mesh selection in the numerical solution of computational problems. We pay most attention to initial-value problems with regular or piecewise regular right-hand side functions.

16.05.2017
Stefan Paszkowski
        Ułamki łańcuchowe skalowane
[Scalable continued fractions]

Streszczenie

Istotną częścią klasycznej teorii liczb było badanie własności ułamków łańcuchowych arytmetycznych (UA) postaci

  a_0+K_{n>0}[1/a_n]    (a_0 całkowite nieujemne, pozostałe a_n naturalne).

M.in. już Lagrange udowodnił, że UA jest okresowy wtedy i tylko wtedy, gdy jego wartość jest niewymiernością kwadratową. Z praktycznego punktu widzenia UA mają pewną wadę: mianowniki a_n mogą być dowolnie duże, co utrudnia ich kodowanie. W komunikacie opisano zmodyfikowane pojęcie: ułamek łańcuchowy skalowany (US). Nie ma on tej wady (a ma inne). Definicja US o danej wartości x>0 wynika wprost z algorytmu podobnego do tego, który prowadzi do UA. Rezultat obliczeń jest liczbą dodatnią T(x), z której można odtworzyć x za pomocą innego algorytmu, wziętego z teorii UA. Podano
  (i) pewne własności T(x); w szczególności jeśli jest to liczba wymierna, to x jest niewymiernością kwadratową,
  (ii) algorytm przejścia od UA do US,
  (iii) przykłady US dla pierwiastka kwadratowego z liczb naturalnych,
  (iv) pytania dotyczące US pozostające jeszcze bez odpowiedzi.

9.05.2017
Andrzej Cegielski (Uniwersytet Zielonogórski)
        Metoda subgradientowa ze sterowaniem poziomu dla zadań minimalizacji wypukłej z ograniczeniami
[A subgradient method with level control for the convex constrained minimization problem]

Streszczenie

Zadanie dopuszczalności wypukłej polega na znalezieniu punktu wspólnego skończenie wielu domkniętych zbiorów wypukłych. W wielu zastosowaniach wymaga się czegoś więcej, a mianowicie znalezienie punktu wspólnego domkniętych zbiorów wypukłych minimalizującego pewną funkcję wypukłą. Wymaganie to prowadzi do metodologii superioryzacji, która umiejscowiona jest pomiędzy metodami dla dopuszczalności wypukłej, a minimalizacją wypukłą z ograniczeniami. Podamy metodę, która sekwencyjnie stosuje algorytm dla ciągu zadań dopuszczalności wypukłej. Metoda używa projekcji subgradientowych ze sterowaniem poziomu oraz ogólniejszych od nich operatorów quasi-nieoddalających, natomiast nie wymaga wyznaczania kosztownych rzutów metrycznych.

25.04.2017
Przemysław Kiciak (Uniwersytet Warszawski)
        Jak zaprojektować powierzchnię gładką
[How to design a smooth surface]

Streszczenie

Tematem referatu jest optymalizacja kształtu powierzchni sklejanych reprezentowanych za pomocą siatek. Funkcjonał, którego minimum jest poszukiwane, jest całką z gradientu krzywizny średniej na powierzchni. Arbitralna topologia powierzchni wymaga, aby płaty wielomianowe wchodzące w skład powierzchni tworzyły połączenia klasy G2. W wystąpieniu opiszę konstrukcję płatów spełniających ten warunek i opartą na niej konstrukcję przestrzeni funkcyjnej będącej podstawą dyskretyzacji zadania wariacyjnego, a także metodę numerycznej optymalizacji.

11.04.2017
Paweł Keller, Iwona Wróbel (Politechnika Warszawska)
        Szczególny, w pełni rekurencyjny algorytm odwracania macierzy trójprzekątniowych.
[A fully recursive algorithm for inverting tridiagonal matrices]

Streszczenie

Jeśli rozważymy dowolną klasę macierzy, która nie zawiera się w zbiorze nieosobliwych macierzy trójkątnych, na przykład wszystkie macierze nieosobliwe, nieosobliwe macierze pasmowe o ustalonej szerokości pasma, to nie stworzono (znanego autorom) jak dotąd algorytmu obliczającego numerycznie macierz odwrotną, dla której oba błędy residuum, ||AX-I|| i ||XA-I|| (X oznacza obliczoną odwrotność A) są zadowalająco małe, to znaczy proporcjonalne do ε*cond(A), gdzie ε jest precyzją obliczeń, a cond(A) wskaźnikiem uwarunkowania macierzy A. Dla każdego znanego algorytmu większy z dwóch powyższych błędów może rosnąć proporcjonalnie do cond(A)2.

W referacie przedstawiony będzie algorytm obliczania odwrotności dowolnej nieosobliwej macierzy trójprzekątniowej, który dzięki starannie dobranym wzorom na obliczanie elementów macierzy odwrotnej zachowuje wszystkie zależności wynikające z równań AX=I=XA, dzięki czemu oba powyższe błędu residuum rosną liniowo z cond(A).

28.03.2017
Przemysław Gospodarczyk, Paweł Woźny
        Zmodyfikowane wielomiany Jacobiego i ich związki z wielomianami Bernsteina
[Modified Jacobi polynomials and their connections with Bernstein polynomials]

Streszczenie

W referacie pokażemy, że zamianę bazy zmodyfikowanych wielomianów Jacobiego na bazę Bernsteina (i odwrotnie) przestrzeni wielomianów stopnia co najwyżej n z ograniczeniami można wykonać w czasie O(n2). W efekcie algorytm obniżania stopnia krzywych Béziera, który przedstawiono w (Bhrawy i inni, J. Comput. Appl. Math. 302 (2016), 369-384), a następnie poprawiono w (Lu i Xiang, J. Comput. Appl. Math. 315 (2017), 65-69), można znacząco usprawnić, ponieważ algorytmy zamiany baz w wymienionych pracach mają złożoność O(n3).

10.01.2017
Filip Chudy
        Grupowanie widmowe
[Spectral Clustering]

Streszczenie

Grupowanie jest jednym z klasycznych problemów uczenia maszynowego. Ostatnimi czasy powodzeniem cieszy się metoda grupowania widmowego. To podejście łączy intuicję stojącą za PCA, grafy i metody numeryczne algebry liniowej, dając algorytm, który uzyskuje bardzo dobre wyniki i wysoką wydajność.

20.12.2016
Paweł Rajba
        Metoda samplingu dla problemów optymalizacyjnych z niepewnymi parametrami
[Sampling method for optimization problems with uncertain parameters]

Streszczenie

W klasycznym modelowaniu problemów optymalizacyjnych przyjmuje się założenie, że parametry są dobrze określone. Jednak rzeczywistość bardzo często wymyka się temu założeniu i mamy wtedy do czynienia z parametrami problemów, które nie są dokładnie określone. Ta niepewność może mieć wiele źródeł, jak np. niedokładność pomiaru, niemożność wyznaczenia dokładnych wartości, przypadkowość, sprzeczność informacji czy subiektywność. Może też być modelowana na różne sposoby. W referacie zostanie zaproponowana metoda samplingu do znajdowania rozwiązań problemów optymalizacyjnych z niepewnymi parametrami modelowanymi przez zmienne losowe. Dodatkowo, poprzez zastosowanie teorii przedziałów ufności czas jej wykonania został poprawiony. Pokażę zastosowanie tej metody do rozwiązania problemu przepływowego z ograniczeniami czasowymi oraz z parametrami modelowanymi przez zmienne losowe o rozkładzie normalnym.

6.12.2016
Piotr Nadybski
        Problemy optymalizacji wykorzystania zasobów we współczesnych rozproszonych systemach przetwarzania danych
[Optimization problem of the efficient resources usage in modern distributed data computing systems]

Streszczenie

W referacie poruszona zostanie tematyka problemu optymalnego planowania procesu wykonywania kopii zapasowych maszyn wirtualnych dla wirtualizatorów z georedundancją. Zaproponowany zostanie algorytm szeregowania zadań dla procesu replikacji oraz zaprezentowane zostaną wyniki badań empirycznych przeprowadzonych przy jego pomocy. W dalszej kolejności zajmiemy się problemem optymalnego wykorzystania zasobów klastra HPC z uwzględnieniem niepewności związanej m.in. z błędnym szacowaniem przez użytkownika zapotrzebowania na zasoby oraz przedstawimy bieżący stan prac autora w tym zakresie. Na zakończenie omówimy dalsze kierunki planowanych badań związanych w wymienioną wyżej problematyką.

22.11.2016
Witold Karczewski
        Zastosowanie metody PCA do analizy wyborów parlamentarnych
[Application of PCA method to the analysis of parliamentary elections]

        Streszczenie

25.10.2016
Zespół ZMN
        Wrażenia z konferencji
[Impressions of summer conferences]