{ "cells": [ { "cell_type": "markdown", "id": "56889fcd-f08a-4475-9928-af817748f5c8", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "cc6e138bded83e62ff3a36a601d06540", "grade": false, "grade_id": "cell-5e2b58ff19f0997c", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "## Numerical Analysis - Fall semester 2025\n", "# Serie 02 - Simple linear systems" ] }, { "cell_type": "markdown", "id": "e59533b3-b808-4126-b177-3390877b24ad", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "10edd7f8d5f42ef44d458651f4e462e8", "grade": false, "grade_id": "cell-e56f5ef08590e711", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "First, we will need to import some of the usual packages. You will have to run this cell every time you restart your notebook." ] }, { "cell_type": "code", "execution_count": null, "id": "5afb622e-c357-4a77-9356-e75ad0400743", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "896fc9aab44afbe84f4354fdd6801bb3", "grade": false, "grade_id": "cell-44ae0a875bc8bfaa", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "import numpy as np\n", "import scipy as sp\n", "import matplotlib.pyplot as plt\n", "import matplotlib\n", "import timeit\n", "import sys" ] }, { "cell_type": "markdown", "id": "292b3b9c-9456-4645-8d7c-0ec4f5b0ba0d", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "7111540313e1e5031fddb3d83d346a4d", "grade": false, "grade_id": "cell-8dd6436372d2524c", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "
\n", "\n", "### Simple linear systems" ] }, { "cell_type": "markdown", "id": "6aeac6d6-19da-4544-a851-80aff6c469b2", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "6f6141f1cbf0c4812370816aefa08d84", "grade": false, "grade_id": "cell-f9b1603e57818fd9", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "Consider the following two linear systems:\n", "\n", "$$\n", " A_1\\mathbf{x} = \\mathbf{b}_1, \\qquad \\text{and} \\qquad\n", " A_1= \\begin{bmatrix}\n", " 2 & 4 & 8 \\\\\n", " 1 & 1 & 4 \\\\\n", " 3 & 6 & 7\n", " \\end{bmatrix}, \\quad\n", " \\mathbf{b}_1 = \\begin{bmatrix} 6 \\\\ 5 \\\\ 4 \\end{bmatrix},\n", "$$\n", "\n", "and\n", "\n", "$$\n", " A_2\\mathbf{x} = \\mathbf{b}_2, \\qquad \\text{and} \\qquad\n", " A_2 = \\begin{bmatrix}\n", " 1 & 1 & 1 & 1 \\\\\n", " 2 & 2 & 5 & 3 \\\\\n", " 4 & 6 & 8 & 0 \\\\\n", " 3 & 3 & 9 & 8\n", " \\end{bmatrix}, \\quad\n", " \\mathbf{b}_2 = \\begin{bmatrix} 1 \\\\ 2 \\\\ 5 \\\\ 0 \\end{bmatrix}.\n", "$$" ] }, { "cell_type": "markdown", "id": "82bd30d7-c89d-45eb-8d16-79c87724c63c", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "497bfa47fcd413f6344ff5d1a354809e", "grade": false, "grade_id": "cell-28b47eb60c1c806f", "locked": true, "points": 0, "schema_version": 3, "solution": false, "task": true } }, "source": [ "
\n", " \n", "**Exercise 1 (Theoretical):** Solve $A_1 \\mathbf{x} = \\mathbf{b}_1$ using Gaussian elimination and determine the LU factorization $A_1 = L_1 U_1$.\n", "
\n" ] }, { "cell_type": "markdown", "id": "3cbfe1a7-8e5d-412f-a287-6a43281927e6", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "05defc748d096fc4e8a77595b8b5e654", "grade": false, "grade_id": "cell-3b6a1d75bfd8b314", "locked": true, "points": 0, "schema_version": 3, "solution": false, "task": true } }, "source": [ "
\n", " \n", "**Exercise 2 (Theoretical):** Solve $A_2 \\mathbf{x} = \\mathbf{b}_2$ using Gaussian elimination with pivoting and determine the LU factorization of $P_2 A_2 = L_2 U_2$.\n", "
\n" ] }, { "cell_type": "markdown", "id": "dfddca72-a5a7-48e6-9cfd-9378d43a487c", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "6fc82035285bcc540691274e358c594d", "grade": false, "grade_id": "cell-218f10fd8ec74a7d", "locked": true, "points": 0, "schema_version": 3, "solution": false, "task": true } }, "source": [ "
\n", " \n", "**Exercise 3 (Theoretical):** Compute the determinant of the matrix $A_2$ using its LU factorization.\n", "\n", "*Hint:* We know that\n", "$$\n", "\\text{det}(A_2)=\\text{det}(P_2^{-1}L_2U_2)=\\displaystyle\\frac{\\text{det}(L_2) \\text{det}(U_2)}{\\text{det}(P_2)}.\n", "$$\n", "
\n" ] }, { "cell_type": "markdown", "id": "81d2b00c-45cd-4d89-ab1c-cc4e306b666f", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "05462597aa89b9dc9beffb7d6f0e8543", "grade": false, "grade_id": "cell-b9890a011292fd00", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "
\n", "\n", "### LU factorization for dense and sparse matrix " ] }, { "cell_type": "markdown", "id": "34866e1d-3d2e-488e-8db1-be7314e6fb54", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "f5c30e0f379c8abb2630b1de68bba752", "grade": false, "grade_id": "cell-ac16c788bf6da4d7", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "
\n", " \n", "**Exercise 4:** Complete the function `binomial_matrix` which creates a matrix $A \\in \\mathbb{R}^{m \\times m}$ whose entries $a_{ij}$ for $i,j = 1, 2, \\dots, m$ independently follow a binomial distribution with $n \\in \\mathbb{N}$ trials and a success probability of $p \\in [0, 1]$. Use your implementation to create the $(n=10, p=0.5)$-binomial matrix $A \\in \\mathbb{R}^{400 \\times 400}$. Visualize its non-zero entries using the function `plt.spy(A)`, which plots the non-zero entries of a matrix in black.\n", "\n", "*Hint:* The NumPy function `np.random.binomial(n, p, (m, m))` outputs an $m \\times m$ NumPy array whose entries are independently $(n, p)$-binomial distributed. The seed of NumPy's random number generator is fixed to `seed=0`, such that you will always get the same random matrix for the same parameters.\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "d240c37e-6e7a-456f-bf74-7402eb39c146", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "5062ca36f86d5ff2adc26abd3f48aaec", "grade": false, "grade_id": "cell-69ad0d0c4384592d", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "def binomial_matrix(m, n, p, seed=0):\n", " np.random.seed(seed)\n", " # YOUR CODE HERE\n", " raise NotImplementedError()\n", "\n", "# YOUR CODE HERE\n", "raise NotImplementedError()" ] }, { "cell_type": "markdown", "id": "f88dbe2d-9085-483a-ab64-8150e87d34cf", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "47809d209b43d76021d949be5fcf1e83", "grade": false, "grade_id": "cell-bce9533bc6dcdf29", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "
\n", " \n", "**Exercise 5:** Compute the LU factorization using the function `sp.linalg.lu`, which takes as an input a matrix $A$ and returns the three matrices $P$, $L$, and $U$ which characterize the LU factorization of $A$. Visualize the non-zero entries of $L$, $U$, and $P$ (again use `plt.spy`). Have row-permutations been performed? How do the number of non-zero elements in $L$ and $U$ compare with what we saw for $A$?\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "fc19547c-088f-4e1b-816f-ecbb47f71a26", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "890609cf10e8c128caa9e00acdfa5122", "grade": false, "grade_id": "cell-467b7459d7bcdec0", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "# YOUR CODE HERE\n", "raise NotImplementedError()" ] }, { "cell_type": "markdown", "id": "acb5d7e4-78fc-4462-abf2-a3fdc3ee6d50", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "535f9200671b4f899e29d01f917cd2f1", "grade": false, "grade_id": "cell-c63d4ea99b0a801a", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "
\n", " \n", "**Exercise 6:** For the binomial matrix $A$ with dimensions $m=20^2, 21^2,\\ldots,35^2$, compute the number of non-zero entries $\\text{nnz}(A)$ in $A$ and compare it to the number of non-zero elements $\\text{nnz}(L) + \\text{nnz}(U)$ in its LU factors. Plot the results in a logarithmic plot, and add the number of entries $m^2$ of the full matrix for comparison.\n", "\n", "*Hint:* Use `np.count_nonzero` to count the number of non-zero entries in a NumPy array.\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "24724b39-0ac7-4fc8-b30a-455567d87933", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "163e959f5d0589a5b94d6619d136bfd1", "grade": false, "grade_id": "cell-b98a075242a67026", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "# YOUR CODE HERE\n", "raise NotImplementedError()" ] }, { "cell_type": "markdown", "id": "e59d4257-2b03-4377-8760-de1d6de9277f", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "146d7f2b97ffbdc3e8c53dacc0526077", "grade": false, "grade_id": "cell-f7e107d62b3543c1", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "Below, we provide you with a function which computes the runtime of the LU factorization algorithm `sp.linalg.lu` for any matrix `A` by executing the function on the matrix multiple times, and averaging the individual runtimes. The number of repetitions of the function execution can be controlled with the argument `repeats`." ] }, { "cell_type": "code", "execution_count": null, "id": "0133d01f-7bf7-499f-8d77-2da5cd7f0402", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "b6adcb85fecb2ff5c4ede3788b77861f", "grade": false, "grade_id": "cell-55565969b2825125", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "def lu_runtime(A, repeats):\n", " t = timeit.timeit(lambda: sp.linalg.lu(A), number=repeats) / repeats\n", " return t" ] }, { "cell_type": "markdown", "id": "b328a03b-a1cd-4696-bc28-2dccaecd62b5", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "92530be0f9b83d2f526ae32746b36543", "grade": false, "grade_id": "cell-79c88eb1fc0ecc84", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "
\n", " \n", "**Exercise 7:** Measure the approximate runtime for computing the LU factorization of the binomial matrix $A$ of dimensions $m=20^2, 21^2,\\ldots,35^2$. Set `repeats=50` to average over $50$ executions of the algorithm to get a more stable estimate of the true run-time.\n", "
" ] }, { "cell_type": "markdown", "id": "64c64a98-b216-4f07-a554-8c76e029a6a8", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "6200e673dc416a679dc3e7734ba6dc51", "grade": false, "grade_id": "cell-4de1828a62d21c86", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "
\n", "\n", "**Note:** It may happen that the runtime of the first $m$ is significantly higher. This is due to the caching which Python performes in the background. If it bothers you, you may simply ignore the first $m$.\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "7d8978a9-20a3-4a8e-bf7b-c98490e0ece4", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "05ecb3869e034e3c6df0c1c8d490320d", "grade": false, "grade_id": "cell-af07e1ccd799913c", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "# YOUR CODE HERE\n", "raise NotImplementedError()" ] }, { "cell_type": "markdown", "id": "b0c6bc08-e93e-483f-8522-f7ba6f3c2249", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "6b4fd87ae6e5b4ef6b2efa5ef73c35a2", "grade": false, "grade_id": "cell-c06bf4068c06f6f7", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "The following function `laplacian_matrix` generates a Laplacian matrix $B \\in \\mathbb{R}^{m \\times m}$." ] }, { "cell_type": "code", "execution_count": null, "id": "1e9a9525-fdd6-4c7f-9752-14b944987bc4", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "b56b72c98840f0e673bbadfdf5ff64fd", "grade": false, "grade_id": "cell-768b7fce1ea61dab", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "def laplacian_matrix(m):\n", " n = int(np.sqrt(m))\n", " d = np.ones(n ** 2)\n", " mat = sp.sparse.spdiags([d, -2 * d, d], [-1, 0, 1], n, n)\n", " I = sp.sparse.eye(n)\n", " A = sp.sparse.kron(I, mat) + sp.sparse.kron(mat, I) \n", " return A.todense()" ] }, { "cell_type": "markdown", "id": "e0612d6d-6a5a-4200-b29c-6dc2630fc6ed", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "68e4c5275b249c3774cd5896a134f165", "grade": false, "grade_id": "cell-0a38a19bf51d0502", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "
\n", " \n", "**Exercise 8:** Repeat all of the above exercises in this section for the Laplacian matrix $B$ with the same dimensions. Compare to the results you've obtained for the binomial matrix $A$.\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "d21bb3a2-1600-43d5-8097-b81f63691dbd", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "847f6bcef112b161489dace5ac88448d", "grade": false, "grade_id": "cell-84676c464c1bde58", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "# YOUR CODE HERE\n", "raise NotImplementedError()" ] }, { "cell_type": "markdown", "id": "2443aa45-0fca-4113-995c-70e9adc40d89", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "2e425cfa3984543087415153e5d55508", "grade": false, "grade_id": "cell-a26fae9678ff662c", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "
\n", "\n", "## The end\n", "\n", "Congratulations! You have made it to the end of the second exercise notebook. " ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.3" } }, "nbformat": 4, "nbformat_minor": 5 }