Trudno sobie wyobrazić współczesną naukę lub biznes oparty na nowoczesnych technologiach bez wspomagania obliczeniami komputerowymi. Istotna część tych rachunków to obliczenia numeryczne, czyli takie, w których działania wykonuje się na liczbach rzeczywistych (zmiennopozycyjnych). W prostych przypadkach takie obliczenia przeprowadzamy w arkuszu kalkulacyjnym, jednak gdy zadanie jest bardziej skomplikowane, musimy uciec się do użycia bardziej wyrafinowanych narzędzi.
Niniejszy serwis gromadzi różne informacje przydatne osobom stosującym metody numeryczne na co dzień. Zapraszam do współredagowania! Zestawiłem tu rozmaite materiały lub linki do innych stron. Materiały własne opracowałem przede wszystkim w ramach wykładu Obliczenia naukowe, prowadzonego przeze mnie przez wiele lat dla studentów wydziału MIM UW. Znalazły się tu także materiały uzupełniające do podręcznika z obliczeń inżynierskich i naukowych, wydanego przez PWN.
O ile inaczej nie stwierdzono, z materiałów tu zamieszczonych możesz korzystać bezpłatnie na zasadach licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
Materiały dostępne w innych serwisach, do których podaję tu linki, mogą być objęte innymi zasadami używania lub rozpowszechniania.
Podręcznik
Zdj.: Wydawnictwo Naukowe PWN
Książka Obliczenia inżynierskie i naukowe (Wydawnictwo Naukowe PWN, 2011) jest przyjaznym Czytelnikowi przewodnikiem po podstawowych narzędziach obliczeń numerycznych. Składa się z trzech części:
- Skuteczne - dotyczącej praktycznego wykorzystania bardzo wygodnych pakietów obliczeń inżynierskich i naukowych: MATLAB-a i Octave;
- Szybkie - omawiającej detale programowania algorytmów numerycznych w języku C, podstawy wykorzystania najbardziej popularnych bibliotek numerycznych, a także najważniejsze metody optymalizacji szybkości działania programów numerycznych;
- Efektowne - przedstawiającej dwa środowiska zaawansowanej wizualizacji danych numerycznych: OpenDX i ParaView.
Dodatki
- Wybrane kody źródłowe programów omawianych w książce
- Errata (plik PDF). Dziękując wszystkim Czytelnikom za dotychczas wskazane błędy, proszę o nadsyłanie informacji o pozostałych na adres poczty elektronicznej podany na końcu strony.
Dema i podręczne instrukcje
- MATLAB i Octave
- Ściągawka z Octave - najważniejsze polecenia Octave na 4 stronach formatu A4 (kod źródłowy TeX)
- Matlab cheat sheet - najważniejsze polecenia MATLAB-a, MIT, 2007
- Przewodniki po MATLAB-ie, opracowane przez producenta (MathWorks). Wszystkie dostępne są ze strony Getting started with MATLAB.
- Learn Octave under 10 minutes (wideo; pierwsze kroki)
- programowanie w C, biblioteki numeryczne
- BLAS - Basic Linear Algebra Subprograms. A Quick Reference Guide - skrótowa ściągawka z podstawowych funkcji BLAS
- LAPACK user's guide - podręcznik (dość wyrobionego) użytkownika LAPACKa
- LAPACK Quick Reference Guide to the Driver Routines (VERSION 3.0) - skrótowa ściągawka z podstawowych funkcji LAPACKa (uwaga: wymaga przeglądarki PostScriptu)
- zaawansowana wizualizacja
- Paraview basics tutorial (wideo)
Strony domowe oprogramowania numerycznego (i nie tylko)
Wybrane strony domowe oprogramowania wykorzystywanego w obliczeniach numerycznych.
Środowiska
Z wielu powodów warto polecić system operacyjny Linux jako najwygodniejszy do prowadzenia obliczeń numerycznych. Spośród wielu wygodnych w użytkowaniu dystrybucji Linuxa polecam Fedorę, Ubuntu i OpenSUSE. Pod Windows możemy też zainstalować Linuxa w maszynie wirtualnej, np. VirtualBox.
Niezależnie od systemu operacyjnego (Linux, Windows, MacOS), wymienione poniżej środowiska obliczeniowe będą nas dobrze wspomagać w pracy:
- MATLAB. Wygodne środowisko prowadzenia obliczeń naukowych i inżynierskich. http://www.mathworks.com/products/matlab/.
- GNU Octave. Wygodne środowisko prowadzenia obliczeń naukowych i inżynierskich. Darmowy klon MATLABa. http://www.gnu.org/software/octave/.
- Octave-forge. Kolekcja rozszerzeń dla Octave. http://octave.sourceforge.io.
- Julia. Coraz bardziej popularne środowisko obliczeniowe, bardzo podobne do MATLAB-a, ale znacznie świeższe i skonstruowane z wykorzystaniem nowoczesnych technologii programistycznych. http://www.julialang.org
- Scilab. Wygodne środowisko prowadzenia obliczeń naukowych i inżynierskich. Pod wieloma względami podobny do MATLABa. http://www.scilab.org.
- Python. Kolekcja modułów NumPy, SciPy i Numba daje dobry start do używania Pythona w zastosowaniach numerycznych. W szczególności, wizualizacja w module Matplotlib wzoruje się na MATLAB-ie/Octave. https://www.python.org/
- SageMath. Kombajn łączący w jednym (Pythonowym) środowisku interfejsy do wielu narzędzi. Jeśli dobrze skonfigurowany, oprócz Pythona i jego modułów, wśród dostępnych pakietów będzie też Octave oraz Maxima. http://www.sagemath.org
Kompilatory i narzędzia wspomagające
- GCC. Kolekcja kompilatorów: C, C++, Fortranu, itd. http://gcc.gnu.org.
- GDB: The GNU Project Debugger. Bardzo dobry debuger. http://www.gnu.org/software/gdb.
- GNU make. Niesamowicie ułatwia kompilację programów złożonych z wielu plików źródłowych i bibliotek. http://www.gnu.org/software/make/.
- Intel Compilers. Kolekcja kompilatorów na procesory x86 i x86-64. W dużym stopniu zgodne z GCC. http://software.intel.com/en-us/intel-compilers/.
- MinGW. Wcielenie GCC dla Windows. http://www.mingw.org
- AMD Optimizing C/C++ Compiler. Kompilator rozwijany przez AMD. https://developer.amd.com/amd-aocc/.
- Valgrind. Narzędzie do profilowania dostępu do pamięci. http://valgrind.org/.
- OProfile. Zaawansowany profiler działania całego systemu. http://oprofile.sourceforge.net/.
- PAPI. Narzędzia profilowania działania programów, m.in. wykorzystuje sprzętowe liczniki flopów i odwołań do pamięci. http://icl.cs.utk.edu/papi/.
Biblioteki ogólnego przeznaczenia/wielozadaniowe
- AMD Math Library (LibM). Numeryczna biblioteka wielozadaniowa, optymalizowana na procesory x86-64. https://developer.amd.com/amd-cpu-libraries/amd-math-library-libm/.
- GMP — the GNU Multiple Precision Arithmetic Library. Pozwala prowadzić obliczenia w dowolnej precyzji, oczywiście ze stratą dla szybkości. http://gmplib.org.
- GSL — GNU Scientific Library. Numeryczna biblioteka wielozadaniowa. http://www.gnu.org/software/gsl.
- HDF5. Narzędzia obsługi zaawansowanego formatu wymiany danych. http://www.hdfgroup.org/HDF5/.
- HSL (Formerly the Harwell Subroutine Library). Numeryczna biblioteka wielozadaniowa. http://www.hsl.rl.ac.uk.
- Intel Math Kernel Library (MKL). Numeryczna biblioteka wielozadaniowa, optymalizowana na procesory Intela. http://software.intel.com/en-us/intel-mkl/.
Macierze, układu równań liniowych, algebra liniowa
Zestaw funkcji realizujących podstawowe zadania algebry liniowej to dziś obowiązkowy składnik numerycznych bibliotek wielozadaniowych.
Warto jednak sprawdzić, czy poszukiwana funkcjonalność nie jest czasem lepiej realizowana przez biblioteki specjalistyczne lub równoległe.
- ARPACK. Wartości i wektory własne macierzy rozrzedzonych http://www.caam.rice.edu/software/ARPACK/.
- ATLAS. Optymalizowana wersja BLAS i LAPACKa http://math-atlas.sourceforge.net/.
- BLAS. Podstawowe procedury działające na wektorach i macierzach. Niezbędne! Warto skorzystać z wersji zoptymalizowanej na daną architekturę (ACML, MKL, ATLAS, OpenBLAS, CUBLAS, ...). http://www.netlib.org/blas.
- SuiteSparse. Procedury obsługi macierzy rzadkich i rozwiązywania układów równań liniowych. http://faculty.cse.tamu.edu/davis/suitesparse.html.
- OpenBLAS. BLAS zoptymalizowany na architektury x86 i x86-64. https://www.openblas.net.
- LAPACK. Klasyczna biblioteka: rozwiązywanie układów równań liniowych, znajdowanie wartości i wektorów własnych, liniowe zadanie najmniejszych kwadratów. Niezbędne! Warto skorzystać z wersji zoptymalizowanej na daną architekturę (ACML, MKL, ...). http://www.netlib.org/lapack.
- MAGMA. Coś w rodzaju okrojonego LAPACKa i BLASów dla systemów heterogenicznych, zawierających m.in. procesory wielordzeniowe. http://icl.cs.utk.edu/magma.
- PARDISO Solver Project. Rozwiązywanie układów równań liniowych z macierzami rzadkimi. http://www.pardiso-project.org/.
- PLASMA. Coś w rodzaju okrojonego LAPACKa (plus BLAS 3) dla procesorów wielordzeniowych. http://icl.cs.utk.edu/plasma.
- Sparse BLAS. BLAS dla macierzy rozrzedzonych. http://math.nist.gov/spblas.
- SuperLU. Rozwiązywanie układów równań liniowych z macierzami rzadkimi. http://crd.lbl.gov/~xiaoye/SuperLU/.
Wizualizacja
- Gnuplot. Prosty program do rysowania wykresów. http://www.gnuplot.info.
- Mayavi Project. Narzędzie do wizualizacji danych. https://docs.enthought.com/mayavi/mayavi/.
- OpenDX. Bardzo dobre środowisko o mnóstwie możliwości. Niestety, nie rozwijane. http://www.opendx.org.
- ParaView. Wygodne środowisko pozwalające przefiltrować dane na wiele sposobów. http://www.paraview.org.
- VisIt Visualization Tool. Narzędzie do wizualizacji danych. http://visit.llnl.gov.
- VisNow. Napisane w Javie narzędzie wizualizacji, opracowane w ICM UW. http://visnow.icm.edu.pl.
- VTK — The Visualization Toolkit. Biblioteka, na której opiera się ParaView. http://www.vtk.org/.
- VTK file formats. Opis formatów danych akceptowanych przez VTK i ParaView. http://www.vtk.org/VTK/img/file-formats.pdf.
Specjalistyczne biblioteki numeryczne
Warto sprawdzić, czy poszukiwana funkcjonalność nie jest czasem realizowana przez biblioteki wielozadaniowe lub przez biblioteki algebry liniowej.
- Netlib Repository. Bardzo bogata kolekcja oprogramowania numerycznego (głównie w Fortranie). http://www.netlib.org.
- COMSOL Multiphysics Modeling and Simulation Software. Rozbudowany Toolbox MATLABa dla symulacji układów złożonych, modelowanych równaniami różniczkowymi cząstkowymi http://www.comsol.com.
- deal.II: A Finite Element Differential Equations Analysis Library. Rozwiązywanie równań różniczkowych cząstkowych metodą elementu skończonego. http://www.dealii.org.
- FFTW. Szybka transformacja Fouriera i tym podobne. Bardzo szybka. http://www.fftw.org/.
- GLPK — GNU Linear Programming Kit. Programowanie liniowe na różne sposoby. http://www.gnu.org/software/glpk/.
- METIS — family of multilevel partitioning algorithms. Dobre algorytmy podziału grafu. http://glaros.dtc.umn.edu/gkhome/views/metis/.
- MINPACK. Minimalizacja funkcji i wyznaczanie miejsc zerowych. Także nieliniowe zadanie najmniejszych kwadratów. http://www.netlib.org/minpack.
- MPFR (Multiple-Precision Floating-point computations with correct Rounding). Nazwa mówi wszystko. http://www.mpfr.org.
- ODEPACK. Klasyczna biblioteka dla równań różniczkowych zwyczajnych, dziś zastąpiona przez SUNDIALS. http://www.netlib.org/odepack, zob. także http://computation.llnl.gov/casc/odepack/odepack_home.html.
- OSKI: Optimized Sparse Kernel Interface. Szybkie mnożenie wielkich macierzy rozrzedzonych przez wektor, plus inne dodatki. http://bebop.cs.berkeley.edu/oski.
- SUNDIALS. Wielkie układy równań różniczkowych zwyczajnych, razem z analizą wrażliwości na zmianę parametrów. Równania nieliniowe. Dodatkowo: Toolbox dla MATLABa (działa też z Octave). https://computation.llnl.gov/casc/sundials/main.html.
- XBLAS — Extra Precise Basic Linear Algebra Subroutines. Nazwa mówi wszystko. http://www.netlib.org/xblas.
Programowanie równoległe i biblioteki wspierające komputery wielordzeniowe/wieloprocesorowe
- AMD CPU Libraries. BLAS, biblioteka matematyczna, FFT, libFLAME dla AMD EPYC. https://developer.amd.com/amd-cpu-libraries/.
- PETSc. Kombajn umożliwiający równoległe rozwiązywanie układów równań pochodzących z metody elementu skończonego na komputerach masywnie równoległych. http://www.mcs.anl.gov/petsc.
- SLEPc. Wartości i wektory własne macierzy rozrzedzonych. http://slepc.upv.es/
- CUDA Toolkit. BLAS, FFT, obsługa macierzy rzadkich, itp. - zoptymalizowane dla GPU NVIDIA, obsługujących CUDA. https://developer.nvidia.com/gpu-accelerated-libraries.
- Intel Threading Building Blocks for Open Source. Wygodne narzędzie programowania komputerów z procesorami wielordzeniowymi. Coś pośredniego między PThreads a OpenMP. http://www.threadingbuildingblocks.org/.
- MPICH. Implementacja MPI. http://www.mpich.org.
- MUMPS: a MUltifrontal Massively Parallel sparse direct Solver. Nazwa mówi wszystko. http://mumps.enseeiht.fr/.
- OpenMP. Bardzo proste narzędzie zrównoleglania kodu, np. na komputery z procesorami wielordzeniowymi. http://openmp.org/.
Przykłady z życia wzięte
Obliczenia inżynierskie i naukowe to nie tylko zwykła znajomość rzemiosła: narzędzi programistycznych i sprzętu komputerowego; to także doświadczenie i pomysłowość, które możemy rozwijać tylko poprzez zetknięcie się z prawdzimymi zadaniami obliczeniowymi. Zamieszczone poniżej, szczegółowo opracowane przykłady konkretnych zadań obliczeniowych, pozwalają zapoznać się z praktyką rozwiązywania problemów z życia wziętych.
Biologia i medycyna
Receptory wzrokowe skrzypłocza
Często zadanie obliczeniowe wydaje się na tyle proste i standardowe, że możemy przeoczyć podstawowe niejasności dotyczące samego sformułowania modelu matematycznego. To może przełożyć się na niespodziewane trudności w numerycznym wyznaczeniu rozwiązań modelu. Warto o tym pamiętać zwłaszcza w naszej sytuacji, gdy coraz mocniejsze komputery zachęcają do coraz większej wiary w skuteczność brutalnej numeryki.
Słowa kluczowe: RRZ, prawidłowe zrozumienie problemu i sformułowanie go w języku matematyki, wizualizacja
Prosty model z opóźnieniem
W MATLABie i w Octave znajdują się także funkcje pozwalające wyznaczać rozwiązania mniej typowych równań różniczkowych zwyczajnych. Warto im się przyjrzeć i zwrócić uwagę na to, że wymagają one znacznie więcej przygotowań niż w przypadku standardowych RRZ.
Słowa kluczowe: RRZzO, wizualizacja
Wyznaczenie parametrów równania Michaelisa—Menten
Dopasowanie krzywej do punktów pomiarowych to chleb powszedni eksperymentatorów. Często można zrobić to na wiele sposobów. Na klasycznym przykładzie porównujemy kilka znanych metod i pokazujemy, jak możemy wykorzystać nowoczesny software, by zrobić to dobrze i sprawnie.
Słowa kluczowe: Liniowe/nieliniowe zadanie dopasowania parametrów, RRZ
Inżynieria
Komunikacja typu klient—serwer
Dopóki nasze symulacje opierają się na niewielu danych i wyznaczają niewiele wyników, wówczas, nawet jeśli wymagają bardzo wielu obliczeń pośrednich, sytuacja pozostaje pod naszą kontrolą i zazwyczaj wystarcza na MATLAB lub Octave. Gdy danych i niewiadomych jest bardzo dużo, sprawy przybierają inny obrót. W prostym koncepcyjnie modelu sieci komunikacyjnej bardzo łatwo o wykładniczy wzrost liczby nieznanych parametrów modelu. Jeśli nie chcemy (lub nie możemy) uprościć samego modelu, musimy wesprzeć się, gdzie trzeba programem w C.
Słowa kluczowe: Hybrydowe programowanie Octave i C (każde z osobna), zagadnienie własne, macierze rzadkie, operacje bitowe, odczyt pliku z parametrami zadania w Octave i w C
Dopasowanie linii i okręgów
Geometryczne zadanie poprowadzenia prostej lub elipsy, czy też dopasowania prostokąta tak, by "najlepiej pasował" do zadanych na płaszczyźnie punktów wydaje się bardzo prostym zadaniem, ale w rzeczywistości, gdy chcemy zrobić to dobrze, musimy chwilę się zastanowić. Na szczęście, w samych obliczeniach możemy potem skutecznie skorzystać z MATLABa lub Octave.
Słowa kluczowe: Nieliniowe zadanie optymalizacji, SVD, wybór i uproszczenia modelu
Transformator
O tym, że można coś policzyć dokładnie, a mimo to zupełnie źle zinterpretować wyniki, traktuje przykład z dziedziny elektrotechniki. Badając rozwiązania równania różniczkowego opisującego charakterystykę transformatora możemy łatwo dać się zwieść elegancji pierwszego uzyskanego wyniku. Co ciekawe, choć same liczby są poprawne, to jednak wykres rozwiązania - już nie... Pokazujemy, jak można próbować to wychwycić.
Słowa kluczowe: RRZ II rzędu, wizualizacja, aliasing, weryfikacja rozwiązań
Rolnictwo
Badanie cech hodowlanych zwierząt
Pokazujemy tu, jak ważne w obliczeniach naukowych jest nie tylko sprawne opanowanie narzędzia obliczeniowego, ale także wiedza o metodach numerycznych. Okazuje się, że najważniejsze jest jednak zrozumienie problemu i dogłębna o nim wiedza: dobry kontakt z Zamawiającym Obliczenia jest bezcenny!
Słowa kluczowe: Zadanie najmniejszych kwadratów, dopasowanie sformułowania modelu do narzędzi numerycznych, metoda iteracyjna
Problemy w badaniach podstawowych (i nie tylko)
Dyfuzja
Bardzo wiele zjawisk jest modelowanych równaniem dyfuzji: wystarczy wspomnieć wyznaczanie rozkładu temperatury w podgrzewanym obiekcie, rozprzestrzeniania się zapachu perfum w powietrzu, czy przenoszenie chorób. Rozważamy dwa podstawowe równania, w których dyfuzja odgrywa kluczową rolę:
- stacjonarne równanie dyfuzji, ze zmiennym współczynnikiem dyfuzji
- ewolucyjne równanie dyfuzji, z dodatkowym uwzględnieniem reakcji (np. chemicznej)
Pokazujemy, jak numerycznie rozwiązywać równanie dyfuzji w przypadku jedno-, dwu- i trójwymiarowym. Choć używamy najprostszych metod (czytaj: najmniej wyrafinowanych i w trudniejszych przypadkach mało skutecznych), i tak zetkniemy się z dość skompilkowanymi zadaniami obliczeniowymi, stanowiącymi duże wyzwanie dla używanych przez nas narzędzi.
» » » Czytaj dalej... » » » o stacjonarnym równaniu dyfuzji
Słowa kluczowe: RRCz eliptyczne liniowe, ze współczynnikiem, w 1D,2D,3D, macierze rzadkie, FFT, metody iteracyjne, ściskanie macierzy, dyskretyzacja
» » » Czytaj dalej... » » ». o ewolucyjnym równaniu dyfuzji
Słowa kluczowe: RRCz paraboliczne nieliniowe, RRZ, instalacja i użytkowanie biblioteki CVODE, wizualizacja w OpenDX i w ParaView, duży program w C, Makefile
Funkcja odwrotna
Wielokrotnie w badaniach naukowych musimy rozwiązać małe, niewinnie wyglądające zadanko. Na przykładzie obliczania funkcji odwrotnej zobaczymy, że i w takich przypadkach możemy natknąć się na smakowite problemy obliczeniowe.
Słowa kluczowe: Skalarne równanie nieliniowe, transformacja zadania do wygodniejszego numerycznie, funkcje anonimowe