{ "cells": [ { "cell_type": "code", "execution_count": 1, "id": "3d06d289", "metadata": { "tags": [ "remove-cell" ] }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "┌ Info: verify download of index files...\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/MatrixDepot.jl:139\n", "┌ Info: reading database\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/download.jl:23\n", "┌ Info: adding metadata...\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/download.jl:67\n", "┌ Info: adding svd data...\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/download.jl:69\n", "┌ Info: writing database\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/download.jl:74\n", "┌ Info: used remote sites are sparse.tamu.edu with MAT index and math.nist.gov with HTML index\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/MatrixDepot.jl:141\n" ] } ], "source": [ "using FundamentalsNumericalComputation\n", "FNC.init_format()" ] }, { "cell_type": "markdown", "id": "3ae206bc", "metadata": {}, "source": [ "(section-krylov-structure)=\n", "# Sparsity and structure\n", "\n", "```{index} ! sparse matrix\n", "```\n", "\n", "Very large matrices cannot be stored all within primary memory of a computer unless they are **sparse**. A sparse matrix has *structural zeros*, meaning entries that are known to be exactly zero.} For instance, the adjacency matrix of a graph has zeros where there are no links in the graph. To store and operate with a sparse matrix efficiently, it is not represented as an array of all of its values. There is a variety of sparse formats available; for the most part, you can imagine that the matrix is stored as triples $(i,j,A_{ij})$ for all the nonzero $(i,j)$ locations.\n", "\n", "## Computing with sparse matrices\n", "\n", "```{index} adjacency matrix\n", "```\n", "\n", "Most graphs with real applications have many fewer edges than the maximum possible $n^2$ for $n$ nodes. Accordingly, their adjacency matrices have mostly zero elements and should be represented sparsely. Julia functions to deal with sparse matrices are found in the `SparseArrays` package in the standard library.\n", "\n", "(demo-structure-sparse)=\n", "```{proof:demo}\n", "```\n", "\n", "```{raw} html\n", "