Two ways:
Get the value of $a_2$ from $(AD)_{12}$ then get $a_4$ from $(AD)_{21} - a_2$
Get the value of $a_6$ from $(AD)_{41}$ then get $a_4$ from $(AD)_{32} - a_6$
$a_4$ cannot be read directly from a single entry, it needs substitutions. This example shows that enabling substitutions allows us to use less colors to find all entries of the Hessian!
How to compute the non-bold entries ?
For star graphs, the entry $a_{uv}$ was the edge of a star with either center $u$ and leaf $v$ or center $v$ and leaf $u$. It was then obtained from the HVP of the color of the center.
We need to generalize this for arbitrary trees. For any edge from a leaf $u$ to a node $v$, we can compute $a_{uv}$ from the $u$th entry of the HVP of color $\phi(v)$. Then, we subtract $a_{uv}$ from the $v$th row of the HVP of color $\phi(u)$. So we can do
$a_{71} \gets (h_\text{red})_7$ then $(h_\text{blue})_1 \gets (h_\text{blue})_1 - a_{71}$
$a_{43} \gets (h_\text{red})_4$ then $(h_\text{blue})_3 \gets (h_\text{blue})_3 - a_{43}$
$a_{52} \gets (h_\text{blue})_5$ then $(h_\text{red})_2 \gets (h_\text{red})_2 - a_{52}$
Then, we can remove these leaves and edges. Doing so, some of their parents in the tree become leaves and we can apply the same procedure recursively. So we get
$a_{12} \gets (h_\text{blue})_5$ then $(h_\text{red})_2 \gets (h_\text{red})_2 - a_{12}$
$a_{32} \gets (h_\text{blue})_5$ then $(h_\text{red})_2 \gets (h_\text{red})_2 - a_{32}$
The value of $(h_{\phi(i)})_i$ is the sum of the entries of the $i$th row of $B_{\phi(i)}$. Since the only nonzero entry of this row is $A_{ii}$, we have $A_{ii} = (h_{\phi(i)})_i$.
The columns 1, 2 and 5 do not share any rows with nonzero entries.
So their entries can be recovered unambiguously with just one JVP!
text/htmlmime,application/vnd.pluto.reactdomelement+objectrootassigneelast_run_timestampAڸ؝Wpersist_js_state·has_pluto_hook_features$39e06fde-d734-11f0-a308-89fba7e8abd6running§runtimel#depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$39e06fde-d734-11f0-a308-89fba7e8abd6depends_on_disabled_cells¦queued¤logsoutputbodyV Sparse AD
Benoît Legat
mimetext/htmlrootassigneelast_run_timestampAڸ ]persist_js_state·has_pluto_hook_features$21898d8d-f822-4128-ad56-d9a10865fb1drunning§runtime KKdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$21898d8d-f822-4128-ad56-d9a10865fb1ddepends_on_disabled_cells¦queued¤logsoutputbody.three_columns (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampAڸ؝f-persist_js_state·has_pluto_hook_features$4f8de444-dcb4-411a-b087-6948699614e0running§runtimeddepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$4f8de444-dcb4-411a-b087-6948699614e0depends_on_disabled_cells¦queued¤logsoutputbodymimetext/plainrootassigneelast_run_timestampAڸ؛枿persist_js_state·has_pluto_hook_features$75597493-3e69-437f-9408-b43a89b35559running§runtimeZdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$75597493-3e69-437f-9408-b43a89b35559depends_on_disabled_cells¦queued¤logsoutputbodymimetext/plainrootassigneelast_run_timestampAڸؚ8persist_js_state·has_pluto_hook_features$9b427766-5290-4dee-8dd5-5aab20080d0arunning§runtime 5{0depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$9b427766-5290-4dee-8dd5-5aab20080d0adepends_on_disabled_cells¦queued¤logsoutputbodyattributesclassstyle#display: flex; flex-direction: row;tagdivchildrenPNG IHDR sRGB gAMA a cHRM z& u0 ` : pQ< IDATxm E:e@g tfRNA^ ` ^U!I IPHҀG6A4ۄf?6aP!I_~fKFp[)ϟXG($i@!I IPHҀB4$ ($i@ iﲄQ<*$i@ __8$ ($i@1&\5IBə[Ҭ%H4$ ($i@!I IPHҀB4x̽IBJ!I IPk W6A{lf5ۄi W6Bə[Ҭ%/֬r ֬r {'xz}/O IPHҀB4$ ($i@!I IPSparse Jacobian
Suppose the Jacobian is sparse.
The sparsity pattern (rows and columns of nonzeros) is known
You want to determine the value of these nonzeros with AD
Sparsity detection of Jacobian
Section 2.4 Consider the adjacency graph $G$ of a matrix $A$ be the graph whose adjacency matrix has same sparsity pattern as $A$. So $i$ and $j$ are adjacent iff $a_{ij}$ is nonzero.
What is the 1-chromatic number of planar graphs ?
The four color theorem shows that the 1-chromatic number of any planar graph $G$ is $\xi_1(G) \le 4$. This theorem is related to our context as it applies to the same coloring problem but the column intersection graphs of sparse matrices are not necessarily scalar hence the chromatic number can be as large as the number of columns of the matrices here.
text/htmlattributesclassstyleflex-grow: 1;tagdivchildren text/html,application/vnd.pluto.reactdomelement+objectڦ
text/htmlmime,application/vnd.pluto.reactdomelement+objectrootassigneelast_run_timestampAڸ؝^{persist_js_state·has_pluto_hook_features$b18a3bf6-102e-49f5-af8c-f1c35d2e2a8brunning§runtime < depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$b18a3bf6-102e-49f5-af8c-f1c35d2e2a8bdepends_on_disabled_cells¦queued¤logsoutputbodyThe sign function is constant over $x > 0$ and $x < 0$ so its output carries no variables
mimetext/htmlrootassigneelast_run_timestampAڸ؝5wհpersist_js_state·has_pluto_hook_features$647c372e-c094-4dfc-8a48-7b7f93fb94ddrunning§runtimeCиdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$647c372e-c094-4dfc-8a48-7b7f93fb94dddepends_on_disabled_cells¦queued¤logsoutputbodyattributesclassstyle#display: flex; flex-direction: row;tagdivchildrenPNG
IHDR 0 sRGB gAMA a cHRM z& u0 ` : pQ<
IDATxiPpZU.C ؗ$ 6Pd3A*B
A*[\kxmqŵ R!H Ak=8Nc=gmhL
$H TR!H TR!H TR!H TR!H Tl 6gA*Bxo } R!H TR!Zý-5B
A*zpz.4zp#TR!H TR!H TR!H TR!H TR!Hp 6_R!H {= m TR!H {k
pcA*B8hgd8l' R!H TR!H TR!H TR!H TR!H A3;1B
A
B
A*Bŵ{[\kx!H T f=gmdk=8A*B
A*B
A*B
A*B
A*B0
1TR!Hp~n H TR!H/f/ q#Q IENDB`image/pngattributesclassstyleflex-grow: 1;tagdivchildren text/html,application/vnd.pluto.reactdomelement+object ,
text/htmlattributesclassstyleflex-grow: 1;tagdivchildren text/html,application/vnd.pluto.reactdomelement+object/PNG
IHDR J sRGB gAMA a cHRM z& u0 ` : pQ< IDATxщ@~Щ* .ؽ$c"RTD*"{w
.HE"R I3'X'1$"RTD*"HE"RTD*"HE"RfNv0 RTD
{6 HE"RxpmTD*"Z 4sx CB*"HE"RTD*"HE"RTD*"Hhds HEްaRTD*"{w
.HE"R I3'X'1$"RTD*"HE"RTD*"HE"RfNv0 RTD
{6 HE"RxpmTD*"Z 4sx CB*"HE"RTD*"HE"RTD*"Hhds HEްaRTD*"&{ IENDB`image/pngmime,application/vnd.pluto.reactdomelement+objectrootassigneelast_run_timestampAڸ؟!persist_js_state·has_pluto_hook_features$4da92dbb-fcbd-4991-a2f1-f866778a27efrunning§runtime jdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$4da92dbb-fcbd-4991-a2f1-f866778a27efdepends_on_disabled_cells¦queued¤logsoutputbody6Utils
Comparison of chromatic numbers
Theorem 7.1 For every graph $G$,
$$\xi_1(G) \le \xi_\text{acyclic}(G) \le \xi_\text{star}(G) \le \xi_2(G) = \xi_1(G^2)$$
Small Example
Star coloring
Definition 4.5 A mapping $\phi: V \to \{1, \ldots, p\}$ is a star coloring if
$\phi$ is a distance-1 coloring
every path of 4 vertices uses at least 3 colors
Theorem 4.6 Let $A$ be a symmetric matrix with nonzero diagonal elements, $G$ be its adjacency matrix. A mapping $\phi$ is a star coloring of the adjacency graph iff it induces a symmetrically structurally orthogonal partition of the columns of $A$.
Name star coloring comes from the fact that the subgraph induced by any pair of colors is a star.
How is the subgraph induced by a pair of colors ?
It does not contain paths of more than 3 vertices and adjacent vertices have opposite colors.
So it is a union of disjoint connected components and each component is a stars with one root node of a given color connected with leaf nodes of the other color.
Coloring of a star
Do we need to aim for distance-2 coloring or does the symmetry of the matrix allows us to relax this ?
What color is your Hessian ?
How many HVP do we need to find the values of this sparse symmetric matrix ?
From which HVP do we determine the off-diagonal entries ?
For the edges 34 and 64, respectively between the yellow nodes 3, 6 and the blue nodes 4, they are part of the star centered at the blue node 4 so they are obtained from the entries 3 and 6 blue HVP.
For the edges 12, 32, 52 and 62, respectively between the yellow nodes 1, 3, 5, 6 and the pink node 2, they are part of the star centered at the pink node 2 so they are obtained from the entries 1, 3, 5 and 6 of the pink HVP.
How is the subgraph induced by a pair of colors ?
It does not contain cycles so it is a union of disjoint trees or in other words a forest.
The concept of tree generalizes the concept of stars. Indeed, a star is a tree and, when rooted at the center of the star, the depth of the tree is 1. Since the depth is one, every edge is incident to a leaf so no substitutions are needed. With acyclic coloring, the edges incident to a leaf will be obtained directly but the edges that are not incident to any tree leaves will need the entries corresponding to the edges deeper in their tree to be determined first.
Three columns in just one JVP
Let $h_c$ be the sum of the columns of $B_c$ hence the result of the corresponding HVP.
What changes with symmetry ?
$$D^\top = \begin{bmatrix} \color{yellow}\mathbf{1} & & & \\ & \color{pink}\mathbf{1} & \color{pink}\mathbf{1} & \\ & & & \color{blue}\mathbf{1} \end{bmatrix} \qquad\qquad\qquad AD = \begin{bmatrix} \color{yellow}a_1 & \color{pink}a_2 + a_3 &\\ \color{yellow}a_2 & \color{pink}a_4 & \color{blue}a_5\\ \color{yellow}a_3 & \color{pink}a_6 &\\ & a_5 & \color{blue}a_7 \end{bmatrix}$$
Illustrative example
scale =
pad =
border =
For any pink node $u > 1$, the offdiagonal entry $a_{u,1}$ can be obtained from the yellow HVP.
text/htmlattributesclassstyleflex-grow: 1;tagdivchildren text/html,application/vnd.pluto.reactdomelement+objectڡ
text/htmlmime,application/vnd.pluto.reactdomelement+objectrootassigneelast_run_timestampAڸ؝^ϰpersist_js_state·has_pluto_hook_features$d0ba0c62-c788-4871-959c-fe7044519849running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$d0ba0c62-c788-4871-959c-fe7044519849depends_on_disabled_cells¦queued¤logsoutputbodyzLess colors but nontrivial substitution
Coloring problems
Given a graph $G(V,E)$,
Nodes $u, v$ are distance $k$ neighbors if there exists a path from $u$ to $v$ of length at most $k$.
A distance-$k$ coloring : mapping $\phi:V \to \{1, \ldots, p\}$ such that $\phi(u) \neq \phi(v)$ whenever $u, v$ are distance-$k$ neighbors.
$k$-chromatic number $\xi_k(G)$ : minimum $p$ such that $\exists$ distance-$k$ coloring with $p$ colors.
Distance-$k$ coloring problem : Find distance-$k$ coloring with fewest colors.
For every fixed integer $k \ge 1$, the distance-$k$ graph coloring problem is NP-hard.
Consider the $4 \times 5$ sparse matrix on the right:
Forward mode would require 5 JVP as there are 5 columns
Reverse mode would require 4 VJP as there are 4 rows
Can we do better using the known sparsity pattern ?
text/htmlmime,application/vnd.pluto.reactdomelement+objectrootassigneelast_run_timestampAڸ؝Wypersist_js_state·has_pluto_hook_features$9df9c76a-48af-4ca6-83f1-b8798d6d4e34running§runtime Idepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$9df9c76a-48af-4ca6-83f1-b8798d6d4e34depends_on_disabled_cells¦queued¤logsoutputbodymimetext/plainrootassigneelast_run_timestampAڸ
˛persist_js_state·has_pluto_hook_features$aeb8b749-006a-400f-9b7d-05333fd7214frunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$aeb8b749-006a-400f-9b7d-05333fd7214fdepends_on_disabled_cells¦queued¤logsoutputbodyhWhole Jacobian in just two JVP
Taken from a tutorial of the SparseMatrixColorings' doc
With star coloring, we need at least 3 colors. With 2 colors, our two forward tangents are
$$D^\top = \begin{bmatrix} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 \end{bmatrix} \qquad\qquad\qquad AD = \begin{bmatrix} a_1 & a_2\\ a_2 + a_4 & a_3\\ a_5 & a_4 + a_6\\ a_6 & a_7 \end{bmatrix}$$
Formulation as coloring problem
Color's columns are structurally orthogonal
Jacobian from 3 JVP
Example
Consider the following sparsity pattern of the Jacobian matrix:
n =
What are the nonzero entries of $i$th row of $B_{\phi(i)}$ ?
It contains $A_{ii}$ but can it contain other nonzero entries ? Suppose that $A_{ij}$ is nonzero with $\phi(j) = \phi(i)$. This would mean that $i$ and $j$ are adjacent and of same color which contradicts the fact that $\phi$ is a distance-1 coloring. So the only nonzero entry of the $i$th row of $B_{\phi(i)}$ is $A_{ii}$.
Definition 4.2 A coloring of the columns of a symmetric matrix $A$ is symmetrically orthogonal if for every nonzero element $a_{uv}$, either (1) there is no other column of color $\phi(u)$ with a nonzero in row $r_u$, or (2) there is no other column of color $\phi(v)$ with a nonzero in row $r_v$.
mimetext/htmlrootassigneelast_run_timestampAڸ؛ypersist_js_state÷has_pluto_hook_features$22c1030b-bef5-4af5-9d5f-6afb4a7ae699running§runtime dpdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$22c1030b-bef5-4af5-9d5f-6afb4a7ae699depends_on_disabled_cells¦queued¤logsoutputbodyÝ
mimetext/htmlrootassigneelast_run_timestampAڸ؝Fupersist_js_state·has_pluto_hook_features$a7e8569e-2fed-4069-aa84-ced67849ab15running§runtime Pdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$a7e8569e-2fed-4069-aa84-ced67849ab15depends_on_disabled_cells¦queued¤logsoutputbodylThe same applies to reverse mode
n =
What color is your Jacobian ?
Given a sparse matrix $A$, two graphs represent its sparsity:
Column intersection graph, used in Software for estimating sparse Jacobian matrices, 1984
Bipartite graph, used in Colpack and SparseMatrixColoring
Scalar example
Larger example : star vs acyclic coloring
Is a coloring of the columns is distance-2 in the adjacency graph iff columns of the same color are structurally orthogonal ?
The adjacency graph $G$ is the quotient graph of the bipartite graph, say $B$, under the identification $r_i \sim a_i$ for all $i$. If the diagonal entries of $A$ are nonzero, for distance-1 neighbors $a_u r_v$ of $B$, we have a distance-2 neighbor $a_ua_v$ of $B$ (with the path $a_ur_v, r_v a_v$). So two nodes are distance-2 neighbors in $G$ iff they are distance-2 neighbors in $B$. As a consequence, the statement is true **if the diagonal entries of $A$ are nonzero. If diagonal entries of $A$ are allowed to be zero, there is the following counter example where both columns are structurally orthogonal even though they are distance 1 neighbors (and hence also distance 2 neighbors).
$$\begin{bmatrix}\cdot & 1\\1 & \cdot\end{bmatrix}$$
For each color $c$, we consider the submatrix $B_c = A_{:,I}$ where $I = \{i \mid \phi(i) = c\}$ is the set of columns corresponding to color-$c$ nodes.
mimetext/htmlrootassigneelast_run_timestampAڸ؝FYͰpersist_js_state·has_pluto_hook_features±published_objectsbondscell_execution_order W$75597493-3e69-437f-9408-b43a89b35559$6bd04f2f-ed5f-4ecf-91dd-8868ec5b83e1$4f8de444-dcb4-411a-b087-6948699614e0$39e06fde-d734-11f0-a308-89fba7e8abd6$e2eb1894-06ad-47a0-9ee0-c65b24a669b5$2578b84a-365a-47b6-b58f-1696517c5d02$874b6593-7310-4788-beb0-2f18c0ca09a7$aeb8b749-006a-400f-9b7d-05333fd7214f$a7e8569e-2fed-4069-aa84-ced67849ab15$18594f1f-6036-4a95-8682-cf415c998311$0a91e27f-3cea-415e-aed4-123482da375a$97c94c5a-fab5-4226-b803-10c85a298f2a$8e2045f3-ee09-4439-b504-d2ca9f58a3dd$fa2a8104-2a3f-438c-bc63-4236a9f5ebeb$9df9c76a-48af-4ca6-83f1-b8798d6d4e34$b18a3bf6-102e-49f5-af8c-f1c35d2e2a8b$f8e9d672-e6ad-4910-8307-2b56616b11bc$7fec005c-11b9-4a75-a93c-195d456db190$d46dcdb3-ac4c-4ba9-ac48-6d6a693630d3$2e3cdd4b-9d04-477c-8c6a-fec6ec846919$1167ae71-b63d-4ccc-a120-31c8483eca85$45f4edeb-d934-413f-9f45-568465111b6e$a3bf5961-323b-4adc-99a0-9a456a0bfd48$a546edb2-6a72-4c5f-95f7-cc7709bbb505$1617c79d-3abe-4ffc-9ee1-3312f2b28eb5$76162106-fb90-4883-b2d2-b87e1419c072$5892dfbb-b375-407b-a0a7-da66adb71b67$e882ebee-36ad-43d9-8ab7-20f7e8b2d9fe$f29078e8-242a-4b88-881f-781829c16ed5$5a6aec48-54fb-4d88-a8a1-b06a2bb99108$19dd6563-1a4e-479f-881d-9bcbc720ea36$32440932-322a-46ce-911d-5fa6a1136bca$c2e4982a-3798-4c45-8831-5a76b3b29f6e$4ab46ef8-0f6e-4e6d-8f6f-ac466977b476$e6697119-2801-48e2-b978-facc00af636d$a7b85908-404b-475b-9875-c1190de5ff71$760ef943-e9d9-4cdc-8977-932cf6fcb78a$285d3797-5086-4adc-839c-2204128585e1$0445aae6-2f7e-42b8-b30b-f31298cdeed0$95d7e9cd-b4a1-4205-b7d4-8c10916be8a2$a4ecf92d-6c45-4112-8f0c-06a6d227cd84$29d9f355-26aa-4714-9f9e-3d020016662e$d0ba0c62-c788-4871-959c-fe7044519849$b33bf212-5f88-47ab-ba10-a2815d17f235$e3ae5697-6b0b-4d5f-99a0-d579b6eff655$f2418632-3261-4acb-8cc6-df333b5480a5$2bd9ea13-362e-47ac-b26d-8e36d33e04ea$e3dec4ca-69c0-4955-9303-5f8a239546f2$d5b7f51b-e451-40a7-aa41-a8006decba33$6c174bac-faef-424a-9de7-e4c7be8ddb27$dbef0e7d-b731-4d83-98e3-104b23f26042$2fe7f4eb-ca33-4338-ba8e-29b769b0dcce$1efb0f40-fb9e-4e5b-be59-84910afbf376$4da92dbb-fcbd-4991-a2f1-f866778a27ef$d23e7238-5edb-42d3-96d9-0dffa9e7f326$e9135060-75d4-4f5a-9315-2e5fbb493cdf$2728dc2c-ca17-4989-9259-451f95a24bd2$352c92ec-14da-4beb-85c4-f66d77fa42d6$a5769449-96cd-477a-bceb-ad9439a37430$cabeb42c-f40b-4549-b9a2-3bda7a988672$22c1030b-bef5-4af5-9d5f-6afb4a7ae699$e820e135-2df2-4fa3-a09b-8ce7e5a1f745$dc23180e-2b0f-41ae-aebf-0159a8f8677a$9e24f674-42af-4fa8-bf3e-42e14d855a58$a01688ec-8f16-4d39-b39d-6d1acd24d7ad$726208c6-e856-42a2-b027-555388bc505e$12ffe7c2-2bf6-4949-ae28-f3d8e03a5da5$21898d8d-f822-4128-ad56-d9a10865fb1d$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166$91226321-fc72-4bd9-8d78-9c2bff5c760a$33b368e7-d71e-40ff-8170-a18d11db98fc$70296870-49af-4564-bdb7-bd2d49f9114b$3e6fc4af-19f4-4ff9-b9cf-759e831ff2a4$647c372e-c094-4dfc-8a48-7b7f93fb94dd$a413c12c-72c1-4f46-b7f2-0b0118c1b232$9b427766-5290-4dee-8dd5-5aab20080d0a$dfe3dffd-926b-4083-9e66-8536e5df198d$b9dc524d-6c0b-4507-842c-b4b6cc90fd96$1f02fda8-6b22-429e-9ef4-243e97372526$592510fd-a0e4-42e5-ae5b-cac301e74f0a$26191290-2b2d-43fe-b2bf-d690fd0bbe15$60070a94-d9ca-474b-9c6f-37468e3f030d$04ea8b79-63ba-4eb4-938c-98a21668924a$e721600c-1887-4e99-b474-a427b665e591$44a6b427-bd4b-4fa1-95d8-a8ea55719192$15cf368c-cada-4a72-b59b-a0f9dd0115b4$79910840-ec59-4433-bfb3-ae2d8da40d22process_statusreadyjulia_versionv1.13.3cell_order W$39e06fde-d734-11f0-a308-89fba7e8abd6$e2eb1894-06ad-47a0-9ee0-c65b24a669b5$2578b84a-365a-47b6-b58f-1696517c5d02$dc23180e-2b0f-41ae-aebf-0159a8f8677a$874b6593-7310-4788-beb0-2f18c0ca09a7$9e24f674-42af-4fa8-bf3e-42e14d855a58$aeb8b749-006a-400f-9b7d-05333fd7214f$a01688ec-8f16-4d39-b39d-6d1acd24d7ad$a7e8569e-2fed-4069-aa84-ced67849ab15$726208c6-e856-42a2-b027-555388bc505e$18594f1f-6036-4a95-8682-cf415c998311$0a91e27f-3cea-415e-aed4-123482da375a$97c94c5a-fab5-4226-b803-10c85a298f2a$8e2045f3-ee09-4439-b504-d2ca9f58a3dd$fa2a8104-2a3f-438c-bc63-4236a9f5ebeb$9df9c76a-48af-4ca6-83f1-b8798d6d4e34$b18a3bf6-102e-49f5-af8c-f1c35d2e2a8b$f8e9d672-e6ad-4910-8307-2b56616b11bc$7fec005c-11b9-4a75-a93c-195d456db190$d46dcdb3-ac4c-4ba9-ac48-6d6a693630d3$2e3cdd4b-9d04-477c-8c6a-fec6ec846919$1167ae71-b63d-4ccc-a120-31c8483eca85$45f4edeb-d934-413f-9f45-568465111b6e$a3bf5961-323b-4adc-99a0-9a456a0bfd48$a546edb2-6a72-4c5f-95f7-cc7709bbb505$352c92ec-14da-4beb-85c4-f66d77fa42d6$a5769449-96cd-477a-bceb-ad9439a37430$1617c79d-3abe-4ffc-9ee1-3312f2b28eb5$76162106-fb90-4883-b2d2-b87e1419c072$5892dfbb-b375-407b-a0a7-da66adb71b67$e882ebee-36ad-43d9-8ab7-20f7e8b2d9fe$f29078e8-242a-4b88-881f-781829c16ed5$5a6aec48-54fb-4d88-a8a1-b06a2bb99108$12ffe7c2-2bf6-4949-ae28-f3d8e03a5da5$91226321-fc72-4bd9-8d78-9c2bff5c760a$19dd6563-1a4e-479f-881d-9bcbc720ea36$32440932-322a-46ce-911d-5fa6a1136bca$c2e4982a-3798-4c45-8831-5a76b3b29f6e$b9dc524d-6c0b-4507-842c-b4b6cc90fd96$4ab46ef8-0f6e-4e6d-8f6f-ac466977b476$e6697119-2801-48e2-b978-facc00af636d$33b368e7-d71e-40ff-8170-a18d11db98fc$1f02fda8-6b22-429e-9ef4-243e97372526$a7b85908-404b-475b-9875-c1190de5ff71$760ef943-e9d9-4cdc-8977-932cf6fcb78a$70296870-49af-4564-bdb7-bd2d49f9114b$285d3797-5086-4adc-839c-2204128585e1$0445aae6-2f7e-42b8-b30b-f31298cdeed0$95d7e9cd-b4a1-4205-b7d4-8c10916be8a2$a4ecf92d-6c45-4112-8f0c-06a6d227cd84$592510fd-a0e4-42e5-ae5b-cac301e74f0a$29d9f355-26aa-4714-9f9e-3d020016662e$3e6fc4af-19f4-4ff9-b9cf-759e831ff2a4$26191290-2b2d-43fe-b2bf-d690fd0bbe15$d0ba0c62-c788-4871-959c-fe7044519849$b33bf212-5f88-47ab-ba10-a2815d17f235$60070a94-d9ca-474b-9c6f-37468e3f030d$647c372e-c094-4dfc-8a48-7b7f93fb94dd$e3ae5697-6b0b-4d5f-99a0-d579b6eff655$04ea8b79-63ba-4eb4-938c-98a21668924a$f2418632-3261-4acb-8cc6-df333b5480a5$cabeb42c-f40b-4549-b9a2-3bda7a988672$2bd9ea13-362e-47ac-b26d-8e36d33e04ea$e721600c-1887-4e99-b474-a427b665e591$e3dec4ca-69c0-4955-9303-5f8a239546f2$44a6b427-bd4b-4fa1-95d8-a8ea55719192$d5b7f51b-e451-40a7-aa41-a8006decba33$22c1030b-bef5-4af5-9d5f-6afb4a7ae699$15cf368c-cada-4a72-b59b-a0f9dd0115b4$6c174bac-faef-424a-9de7-e4c7be8ddb27$a413c12c-72c1-4f46-b7f2-0b0118c1b232$9b427766-5290-4dee-8dd5-5aab20080d0a$dbef0e7d-b731-4d83-98e3-104b23f26042$2fe7f4eb-ca33-4338-ba8e-29b769b0dcce$1efb0f40-fb9e-4e5b-be59-84910afbf376$79910840-ec59-4433-bfb3-ae2d8da40d22$4da92dbb-fcbd-4991-a2f1-f866778a27ef$d23e7238-5edb-42d3-96d9-0dffa9e7f326$75597493-3e69-437f-9408-b43a89b35559$6bd04f2f-ed5f-4ecf-91dd-8868ec5b83e1$4f8de444-dcb4-411a-b087-6948699614e0$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166$e9135060-75d4-4f5a-9315-2e5fbb493cdf$2728dc2c-ca17-4989-9259-451f95a24bd2$e820e135-2df2-4fa3-a09b-8ce7e5a1f745$21898d8d-f822-4128-ad56-d9a10865fb1d$dfe3dffd-926b-4083-9e66-8536e5df198dcell_inputs W$e3ae5697-6b0b-4d5f-99a0-d579b6eff655metadatadisabled©show_logsîskip_as_script§cell_id$e3ae5697-6b0b-4d5f-99a0-d579b6eff655code_foldedäcodemd"""## Acyclic coloring
[Definition 6.3](https://epubs.siam.org/doi/10.1137/S0036144504444711) A mapping ``\phi: V \to \{1, \ldots, p\}`` is an *acyclic coloring* if
1. ``\phi`` is a distance-1 coloring
2. every **cycle** uses at least 3 colors
[Theorem 4.6](https://epubs.siam.org/doi/10.1137/S0036144504444711)
Let ``A`` be a symmetric matrix with **nonzero diagonal elements**,
``G`` be its adjacency matrix. A mapping ``\phi`` is an acyclic coloring of the adjacency graph iff it induces a substitutable partition of the columns of ``A``.
Name acyclic coloring comes from the fact that the subgraph induced by any pair of colors is a forest.
"""$a546edb2-6a72-4c5f-95f7-cc7709bbb505metadatadisabled©show_logsîskip_as_script§cell_id$a546edb2-6a72-4c5f-95f7-cc7709bbb505code_folded¤codeF(xtracer)$d5b7f51b-e451-40a7-aa41-a8006decba33metadatadisabled©show_logsîskip_as_script§cell_id$d5b7f51b-e451-40a7-aa41-a8006decba33code_foldedäcodeXmd"""## Red-Blue subgraph
To compute an off-diagonal entry ``A_{ij}``, consider the subgraph induced by the two colors ``\phi(i)`` and ``\phi(j)``. The entry will be computed, from ``B_{\phi(i)}`` and ``B_{\phi(j)}``, possible after substitution.
Consider below left ``B_\text{red}`` and right ``B_\text{blue}``. The rows corresponding to diagonal entries have been omitted as we already found how to compute them in the previous slide. The rows corresponding to green nodes are in bold as they will be computed from the subgraph induced by red/green or blue/green so we can ignore them for now.
"""$5892dfbb-b375-407b-a0a7-da66adb71b67metadatadisabled©show_logsîskip_as_script§cell_id$5892dfbb-b375-407b-a0a7-da66adb71b67code_foldedäcode2md"""
[**Theorem 3.5**](https://epubs.siam.org/doi/10.1137/S0036144504444711) A coloring of the columns is distance-2 in the bipartite graph iff columns of the same color are structurally orthogonal.
Let the ``k``-th power ``G^k`` of a graph ``G`` be the graph with same nodes as ``G`` and an edge in ``G^k`` for each distance ``k`` neighbors in ``G``.
[**Lemma 3.7**](https://epubs.siam.org/doi/10.1137/S0036144504444711) The column intersection graph is the square of the biparted graph restricted to its column vertices.
[**Lemma 2.1**](https://epubs.siam.org/doi/10.1137/S0036144504444711) A coloring is distance-``k`` in ``G`` iff it is distance-1 in ``G^k``.
**Corollary** A coloring of the columns is distance-1 in the column intersection graph iff columns of the same color are structurally orthogonal.
"""$1f02fda8-6b22-429e-9ef4-243e97372526metadatadisabled©show_logsîskip_as_script§cell_id$1f02fda8-6b22-429e-9ef4-243e97372526code_foldedäcodeqa(md"Is this a distance-2 coloring ? Can we deduce all values of the hessian given the values of ``AD``.", md"""
It is not a distance-2 coloring because the nodes 2 and 3 are distance 2 neighbors. Because of this, in the first row of the second column of ``AD`` we get ``a_2 + a_3`` which prevents us distinguish ``a_2`` or ``a_3``.
However, ``a_2`` and ``a_3`` can be obtained from the first column of ``AD`` so we can retrieve all values of the Hessian from ``AD``.
""")$1167ae71-b63d-4ccc-a120-31c8483eca85metadatadisabled©show_logsîskip_as_script§cell_id$1167ae71-b63d-4ccc-a120-31c8483eca85code_folded¤codeytracer = f(xtracer)$45f4edeb-d934-413f-9f45-568465111b6emetadatadisabled©show_logsîskip_as_script§cell_id$45f4edeb-d934-413f-9f45-568465111b6ecode_foldedäcode/md"## Sparsity detection with multiple outputs"$a413c12c-72c1-4f46-b7f2-0b0118c1b232metadatadisabled©show_logsîskip_as_script§cell_id$a413c12c-72c1-4f46-b7f2-0b0118c1b232code_foldedäcodeSviz(large, decompression = :direct, structure = :symmetric, plot_size = (6cm, 6cm))$60070a94-d9ca-474b-9c6f-37468e3f030dmetadatadisabled©show_logsîskip_as_script§cell_id$60070a94-d9ca-474b-9c6f-37468e3f030dcode_foldedäcodeqa(md"How do we get the value of ``a_4`` ?",
md"""
Two ways:
1) Get the value of ``a_2`` from ``(AD)_{12}`` then get ``a_4`` from ``(AD)_{21} - a_2``
2) Get the value of ``a_6`` from ``(AD)_{41}`` then get ``a_4`` from ``(AD)_{32} - a_6``
``a_4`` cannot be read directly from a single entry, it needs **substitutions**. This example shows that enabling substitutions allows us to use less colors to find all entries of the Hessian!
""")$15cf368c-cada-4a72-b59b-a0f9dd0115b4metadatadisabled©show_logsîskip_as_script§cell_id$15cf368c-cada-4a72-b59b-a0f9dd0115b4code_foldedäcodeqa(
md"How to compute the non-bold entries ?",
md"""
For star graphs, the entry ``a_{uv}`` was the edge of a star with either center ``u`` and leaf ``v`` or center ``v`` and leaf ``u``.
It was then obtained from the HVP of the color of the center.
We need to generalize this for arbitrary trees.
For any edge from a leaf ``u`` to a node ``v``, we can compute
``a_{uv}`` from the ``u``th entry of the HVP of color ``\phi(v)``.
Then, we subtract ``a_{uv}`` from the ``v``th row of the HVP of color ``\phi(u)``.
So we can do
* ``a_{71} \gets (h_\text{red})_7`` then ``(h_\text{blue})_1 \gets (h_\text{blue})_1 - a_{71}``
* ``a_{43} \gets (h_\text{red})_4`` then ``(h_\text{blue})_3 \gets (h_\text{blue})_3 - a_{43}``
* ``a_{52} \gets (h_\text{blue})_5`` then ``(h_\text{red})_2 \gets (h_\text{red})_2 - a_{52}``
Then, we can remove these leaves and edges. Doing so, some of their parents in the tree become leaves and we can apply the same procedure recursively. So we get
* ``a_{12} \gets (h_\text{blue})_5`` then ``(h_\text{red})_2 \gets (h_\text{red})_2 - a_{12}``
* ``a_{32} \gets (h_\text{blue})_5`` then ``(h_\text{red})_2 \gets (h_\text{red})_2 - a_{32}``
""",
)$2fe7f4eb-ca33-4338-ba8e-29b769b0dccemetadatadisabled©show_logsîskip_as_script§cell_id$2fe7f4eb-ca33-4338-ba8e-29b769b0dccecode_foldedäcodeElarge = sparse(Symmetric(sprand(StableRNG(0), Bool, n, n, 0.2) + I));$a3bf5961-323b-4adc-99a0-9a456a0bfd48metadatadisabled©show_logsîskip_as_script§cell_id$a3bf5961-323b-4adc-99a0-9a456a0bfd48code_folded¤code2F(x) = [x[1]*x[2]+sign(x[3]), sign(x[3]) * x[4]/2]$44a6b427-bd4b-4fa1-95d8-a8ea55719192metadatadisabled©show_logsîskip_as_script§cell_id$44a6b427-bd4b-4fa1-95d8-a8ea55719192code_foldedäcodeqa(md"How can the diagonal entries be determined ?", md"""
The value of ``(h_{\phi(i)})_i`` is the sum of the entries of the ``i``th row of ``B_{\phi(i)}``.
Since the only nonzero entry of this row is ``A_{ii}``, we have ``A_{ii} = (h_{\phi(i)})_i``.
""")$9e24f674-42af-4fa8-bf3e-42e14d855a58metadatadisabled©show_logsîskip_as_script§cell_id$9e24f674-42af-4fa8-bf3e-42e14d855a58code_foldedäcodetwo_columns(
md"""
* The columns 1, 2 and 5 do not share any rows with nonzero entries.
* So their entries can be recovered unambiguously with just one JVP!
""",
img("https://iclr-blogposts.github.io/2025/assets/img/2025-04-28-sparse-autodiff/sparse_ad.svg", :width => 400),
)$39e06fde-d734-11f0-a308-89fba7e8abd6metadatadisabled©show_logsîskip_as_script§cell_id$39e06fde-d734-11f0-a308-89fba7e8abd6code_foldedäcodeٻ@htl("""
Sparse AD
Benoît Legat
$(PlutoTeachingTools.ChooseDisplayMode()) $(PlutoUI.TableOfContents(depth=1)) """)$21898d8d-f822-4128-ad56-d9a10865fb1dmetadatadisabled©show_logsîskip_as_script§cell_id$21898d8d-f822-4128-ad56-d9a10865fb1dcode_foldedäcode٨three_columns(left, center, right) = hbox([ left, Div(html" ", style = Dict("flex-grow" => "1")), center, Div(html" ", style = Dict("flex-grow" => "1")), right, ])$4f8de444-dcb4-411a-b087-6948699614e0metadatadisabled©show_logsîskip_as_script§cell_id$4f8de444-dcb4-411a-b087-6948699614e0code_folded¤code2using Graphs, GraphPlot, LinearAlgebra, StableRNGs$75597493-3e69-437f-9408-b43a89b35559metadatadisabled©show_logsîskip_as_script§cell_id$75597493-3e69-437f-9408-b43a89b35559code_folded¤codeOusing PlutoUI, PlutoUI.ExperimentalLayout, HypertextLiteral, PlutoTeachingTools$9b427766-5290-4dee-8dd5-5aab20080d0ametadatadisabled©show_logsîskip_as_script§cell_id$9b427766-5290-4dee-8dd5-5aab20080d0acode_foldedäcodeYviz(large, decompression = :substitution, structure = :symmetric, plot_size = (6cm, 6cm))$2578b84a-365a-47b6-b58f-1696517c5d02metadatadisabled©show_logsîskip_as_script§cell_id$2578b84a-365a-47b6-b58f-1696517c5d02code_foldedäcodemd""" # Sparse Jacobian Suppose the Jacobian is **sparse**. * The *sparsity pattern* (rows and columns of nonzeros) is **known** * You want to determine the **value** of these nonzeros with AD """$dfe3dffd-926b-4083-9e66-8536e5df198dmetadatadisabled©show_logsîskip_as_script§cell_id$dfe3dffd-926b-4083-9e66-8536e5df198dcode_foldedäcodebegin function qa(question, answer) return @htl("$question
$answer` if `question.content[]` is `Markdown.Paragraph` # This will print the question on a new line and we don't want that: h = HTML(_inline_html(question.content[])) return qa(h, answer) end end$18594f1f-6036-4a95-8682-cf415c998311metadatadisabled©show_logsîskip_as_script§cell_id$18594f1f-6036-4a95-8682-cf415c998311code_foldedäcode$md"# Sparsity detection of Jacobian"$e2eb1894-06ad-47a0-9ee0-c65b24a669b5metadatadisabled©show_logsîskip_as_script§cell_id$e2eb1894-06ad-47a0-9ee0-c65b24a669b5code_foldedäcode\md""" * [What color is your Jacobian ? Graph Coloring for Computing Derivatives](https://epubs.siam.org/doi/10.1137/S0036144504444711) * [An Illustrated Guide to Automatic Sparse Differentiation](https://iclr-blogposts.github.io/2025/blog/sparse-autodiff/) * [Revisiting Sparse Matrix Coloring and Bicoloring](https://arxiv.org/abs/2505.07308) """$32440932-322a-46ce-911d-5fa6a1136bcametadatadisabled©show_logsîskip_as_script§cell_id$32440932-322a-46ce-911d-5fa6a1136bcacode_foldedäcode6ijkl = sparse([ 1 2 3 0 2 4 0 5 3 0 6 0 0 5 0 7 ])$c2e4982a-3798-4c45-8831-5a76b3b29f6emetadatadisabled©show_logsîskip_as_script§cell_id$c2e4982a-3798-4c45-8831-5a76b3b29f6ecode_foldedäcodemd"[Section 2.4](https://epubs.siam.org/doi/10.1137/S0036144504444711) Consider the *adjacency graph* ``G`` of a matrix ``A`` be the graph whose adjacency matrix has same sparsity pattern as ``A``. So ``i`` and ``j`` are adjacent iff ``a_{ij}`` is nonzero."$79910840-ec59-4433-bfb3-ae2d8da40d22metadatadisabled©show_logsîskip_as_script§cell_id$79910840-ec59-4433-bfb3-ae2d8da40d22code_foldedäcodeqa(md""" What is the 1-chromatic number of planar graphs ? """, md""" The [four color theorem](https://en.wikipedia.org/wiki/Four_color_theorem) shows that the 1-chromatic number of any planar graph ``G`` is ``\xi_1(G) \le 4``. This theorem is related to our context as it applies to the **same** coloring problem but the column intersection graphs of sparse matrices are not necessarily scalar hence the chromatic number can be as large as the number of columns of the matrices here. """)$5a6aec48-54fb-4d88-a8a1-b06a2bb99108metadatadisabled©show_logsîskip_as_script§cell_id$5a6aec48-54fb-4d88-a8a1-b06a2bb99108code_foldedäcodeOS = sparse([ 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 1 1 0 0 0 ])$726208c6-e856-42a2-b027-555388bc505emetadatadisabled©show_logsîskip_as_script§cell_id$726208c6-e856-42a2-b027-555388bc505ecode_foldedäcodetwo_columns( img("https://iclr-blogposts.github.io/2025/assets/img/2025-04-28-sparse-autodiff/sparse_ad_reverse_full.svg"), img("https://iclr-blogposts.github.io/2025/assets/img/2025-04-28-sparse-autodiff/sparse_ad_reverse_decompression.svg"), )$b18a3bf6-102e-49f5-af8c-f1c35d2e2a8bmetadatadisabled©show_logsîskip_as_script§cell_id$b18a3bf6-102e-49f5-af8c-f1c35d2e2a8bcode_foldedäcodeemd"The sign function is constant over ``x > 0`` and ``x < 0`` so its output carries **no** variables"$352c92ec-14da-4beb-85c4-f66d77fa42d6metadatadisabled©show_logsîskip_as_script§cell_id$352c92ec-14da-4beb-85c4-f66d77fa42d6code_foldedäcodesimg("https://iclr-blogposts.github.io/2025/assets/img/2025-04-28-sparse-autodiff/compute_graph.png", :width => 330)$647c372e-c094-4dfc-8a48-7b7f93fb94ddmetadatadisabled©show_logsîskip_as_script§cell_id$647c372e-c094-4dfc-8a48-7b7f93fb94ddcode_foldedäcodeXviz(ijkl, decompression = :substitution, structure = :symmetric, plot_size = (4cm, 4cm))$4da92dbb-fcbd-4991-a2f1-f866778a27efmetadatadisabled©show_logsîskip_as_script§cell_id$4da92dbb-fcbd-4991-a2f1-f866778a27efcode_foldedäcodemd"## Utils"$e820e135-2df2-4fa3-a09b-8ce7e5a1f745metadatadisabled©show_logsîskip_as_script§cell_id$e820e135-2df2-4fa3-a09b-8ce7e5a1f745code_foldedäcodedtwo_columns(left, right) = hbox([ left, Div(html" ", style = Dict("flex-grow" => "1")), right, ])$1efb0f40-fb9e-4e5b-be59-84910afbf376metadatadisabled©show_logsîskip_as_script§cell_id$1efb0f40-fb9e-4e5b-be59-84910afbf376code_foldedäcodemd""" ## Comparison of chromatic numbers [Theorem 7.1](https://epubs.siam.org/doi/10.1137/S0036144504444711) For every graph ``G``, ```math \xi_1(G) \le \xi_\text{acyclic}(G) \le \xi_\text{star}(G) \le \xi_2(G) = \xi_1(G^2) ``` """$2728dc2c-ca17-4989-9259-451f95a24bd2metadatadisabled©show_logsîskip_as_script§cell_id$2728dc2c-ca17-4989-9259-451f95a24bd2code_foldedäcodesbegin struct Path path::String end function imgpath(path::Path) file = path.path if !('.' in file) file = file * ".png" end return joinpath(joinpath(@__DIR__, "images", file)) end function img(path::Path, args...; kws...) return PlutoUI.LocalResource(imgpath(path), args...) end struct URL url::String end function save_image(url::URL, html_attributes...; name = split(url.url, '/')[end], kws...) path = joinpath("cache", name) return PlutoTeachingTools.RobustLocalResource(url.url, path, html_attributes...), path end function img(url::URL, args...; kws...) r, _ = save_image(url, args...; kws...) return @htl("$r") end function img(file::String, args...; kws...) if startswith(file, "http") img(URL(file), args...; kws...) else img(Path(file), args...; kws...) end end end$33b368e7-d71e-40ff-8170-a18d11db98fcmetadatadisabled©show_logsîskip_as_script§cell_id$33b368e7-d71e-40ff-8170-a18d11db98fccode_foldedäcodeRviz(ijkl, decompression = :direct, structure = :symmetric, plot_size = (3cm, 3cm))$29d9f355-26aa-4714-9f9e-3d020016662emetadatadisabled©show_logsîskip_as_script§cell_id$29d9f355-26aa-4714-9f9e-3d020016662ecode_foldedäcodemd"## Small Example"$e9135060-75d4-4f5a-9315-2e5fbb493cdfmetadatadisabled©show_logsîskip_as_script§cell_id$e9135060-75d4-4f5a-9315-2e5fbb493cdfcode_foldedäcodemfunction colored_plots(A; decompression, structure, partition = :column, kws...) problem = ColoringProblem(; structure, partition) algo = GreedyColoringAlgorithm(; decompression) result = coloring(A, problem, algo) background_color = RGBA(0, 0, 0, 0) border_color = RGB(0, 0, 0) colorscheme = distinguishable_colors( ncolors(result), [convert(RGB, background_color), convert(RGB, border_color)]; dropseed=true, ) A_img, B_img = SparseMatrixColorings.show_colors(result; colorscheme, scale, pad, border, background_color, border_color) if structure == :symmetric S = A else if partition == :column S = A' * A else S = A * A' end end adj = SparseMatrixColorings.AdjacencyGraph(A) G = Graphs.SimpleDiGraph(S - Diagonal(diag(S))) gp = gplot(G; nodefillc = colorscheme[result.color], nodelabel=1:Graphs.nv(G), kws...) A_img, gp, B_img end$a4ecf92d-6c45-4112-8f0c-06a6d227cd84metadatadisabled©show_logsîskip_as_script§cell_id$a4ecf92d-6c45-4112-8f0c-06a6d227cd84code_foldedäcodemd"""## Star coloring [Definition 4.5](https://epubs.siam.org/doi/10.1137/S0036144504444711) A mapping ``\phi: V \to \{1, \ldots, p\}`` is a *star coloring* if 1. ``\phi`` is a distance-1 coloring 2. every **path of 4 vertices** uses at least 3 colors [Theorem 4.6](https://epubs.siam.org/doi/10.1137/S0036144504444711) Let ``A`` be a symmetric matrix with **nonzero diagonal elements**, ``G`` be its adjacency matrix. A mapping ``\phi`` is a star coloring of the adjacency graph iff it induces a symmetrically structurally orthogonal partition of the columns of ``A``. Name star coloring comes from the fact that the subgraph induced by any pair of colors is a star. """$592510fd-a0e4-42e5-ae5b-cac301e74f0ametadatadisabled©show_logsîskip_as_script§cell_id$592510fd-a0e4-42e5-ae5b-cac301e74f0acode_foldedäcodeEqa(md"How is the subgraph induced by a pair of colors ?", md""" It does not contain paths of more than 3 vertices and adjacent vertices have opposite colors. So it is a union of disjoint connected components and each component is a stars with one root node of a given color connected with leaf nodes of the other color. """)$d46dcdb3-ac4c-4ba9-ac48-6d6a693630d3metadatadisabled©show_logsîskip_as_script§cell_id$d46dcdb3-ac4c-4ba9-ac48-6d6a693630d3code_folded¤code$f(x) = x[1] + x[2]*x[3] * sign(x[4])$760ef943-e9d9-4cdc-8977-932cf6fcb78ametadatadisabled©show_logsîskip_as_script§cell_id$760ef943-e9d9-4cdc-8977-932cf6fcb78acode_foldedäcodemd"## Coloring of a star"$2e3cdd4b-9d04-477c-8c6a-fec6ec846919metadatadisabled©show_logsîskip_as_script§cell_id$2e3cdd4b-9d04-477c-8c6a-fec6ec846919code_folded¤codeمxtracer = [ MyGradientTracer(Set(1)), MyGradientTracer(Set(2)), MyGradientTracer(Set(3)), MyGradientTracer(Set(4)), ]$4ab46ef8-0f6e-4e6d-8f6f-ac466977b476metadatadisabled©show_logsîskip_as_script§cell_id$4ab46ef8-0f6e-4e6d-8f6f-ac466977b476code_foldedäcodejmd"Do we need to aim for distance-2 coloring or does the symmetry of the matrix allows us to relax this ?"$19dd6563-1a4e-479f-881d-9bcbc720ea36metadatadisabled©show_logsîskip_as_script§cell_id$19dd6563-1a4e-479f-881d-9bcbc720ea36code_foldedäcodezmd""" # What color is your Hessian ? How many HVP do we need to find the values of this sparse **symmetric** matrix ? """$26191290-2b2d-43fe-b2bf-d690fd0bbe15metadatadisabled©show_logsîskip_as_script§cell_id$26191290-2b2d-43fe-b2bf-d690fd0bbe15code_foldedäcodeqa(md"From which HVP do we determine the off-diagonal entries ?", md""" * For the edges 34 and 64, respectively between the yellow nodes 3, 6 and the blue nodes 4, they are part of the star centered at the blue node 4 so they are obtained from the entries 3 and 6 blue HVP. * For the edges 12, 32, 52 and 62, respectively between the yellow nodes 1, 3, 5, 6 and the pink node 2, they are part of the star centered at the pink node 2 so they are obtained from the entries 1, 3, 5 and 6 of the pink HVP. """)$04ea8b79-63ba-4eb4-938c-98a21668924ametadatadisabled©show_logsîskip_as_script§cell_id$04ea8b79-63ba-4eb4-938c-98a21668924acode_foldedäcoderqa(md"How is the subgraph induced by a pair of colors ?", md""" It does not contain cycles so it is a union of disjoint trees or in other words a forest. The concept of tree generalizes the concept of stars. Indeed, a star is a tree and, when rooted at the center of the star, the depth of the tree is 1. Since the depth is one, every edge is incident to a leaf so no substitutions are needed. With acyclic coloring, the edges incident to a leaf will be obtained directly but the edges that are not incident to any tree leaves will need the entries corresponding to the edges deeper in their tree to be determined first. """)$874b6593-7310-4788-beb0-2f18c0ca09a7metadatadisabled©show_logsîskip_as_script§cell_id$874b6593-7310-4788-beb0-2f18c0ca09a7code_foldedäcode$md"## Three columns in just one JVP"$e3dec4ca-69c0-4955-9303-5f8a239546f2metadatadisabled©show_logsîskip_as_script§cell_id$e3dec4ca-69c0-4955-9303-5f8a239546f2code_foldedäcode_md"Let ``h_c`` be the sum of the columns of ``B_c`` hence the result of the corresponding HVP."$e6697119-2801-48e2-b978-facc00af636dmetadatadisabled©show_logsîskip_as_script§cell_id$e6697119-2801-48e2-b978-facc00af636dcode_foldedäcodemd""" ## What changes with symmetry ? ```math D^\top = \begin{bmatrix} \color{yellow}\mathbf{1} & & & \\ & \color{pink}\mathbf{1} & \color{pink}\mathbf{1} & \\ & & & \color{blue}\mathbf{1} \end{bmatrix} \qquad\qquad\qquad AD = \begin{bmatrix} \color{yellow}a_1 & \color{pink}a_2 + a_3 &\\ \color{yellow}a_2 & \color{pink}a_4 & \color{blue}a_5\\ \color{yellow}a_3 & \color{pink}a_6 &\\ & a_5 & \color{blue}a_7 \end{bmatrix} ``` """$f2418632-3261-4acb-8cc6-df333b5480a5metadatadisabled©show_logsîskip_as_script§cell_id$f2418632-3261-4acb-8cc6-df333b5480a5code_foldedäcodemd"## Illustrative example"$d23e7238-5edb-42d3-96d9-0dffa9e7f326metadatadisabled©show_logsîskip_as_script§cell_id$d23e7238-5edb-42d3-96d9-0dffa9e7f326code_foldedäcodeٲhbox([ md"scale = $(@bind(scale, Slider(1:15, default = 10)))", md"pad = $(@bind(pad, Slider(1:10, default = 3)))", md"border = $(@bind(border, Slider(1:5, default = 2)))", ])$285d3797-5086-4adc-839c-2204128585e1metadatadisabled©show_logsîskip_as_script§cell_id$285d3797-5086-4adc-839c-2204128585e1code_foldedäcodeomd""" * For any pink node ``u > 1``, the offdiagonal entry ``a_{u,1}`` can be obtained from the yellow HVP. """$a01688ec-8f16-4d39-b39d-6d1acd24d7admetadatadisabled©show_logsîskip_as_script§cell_id$a01688ec-8f16-4d39-b39d-6d1acd24d7adcode_foldedäcodetwo_columns( img("https://iclr-blogposts.github.io/2025/assets/img/2025-04-28-sparse-autodiff/sparse_ad_forward_full.svg", :width => 300), img("https://iclr-blogposts.github.io/2025/assets/img/2025-04-28-sparse-autodiff/sparse_ad_forward_decompression.svg", :width => 300), )$d0ba0c62-c788-4871-959c-fe7044519849metadatadisabled©show_logsîskip_as_script§cell_id$d0ba0c62-c788-4871-959c-fe7044519849code_foldedäcode3md""" # Less colors but nontrivial substitution """$1617c79d-3abe-4ffc-9ee1-3312f2b28eb5metadatadisabled©show_logsîskip_as_script§cell_id$1617c79d-3abe-4ffc-9ee1-3312f2b28eb5code_foldedäcodemd""" ## Coloring problems Given a graph ``G(V,E)``, * Nodes ``u, v`` are distance ``k`` neighbors if there exists a path from ``u`` to ``v`` of length at most ``k``. * A *distance-*``k`` coloring : mapping ``\phi:V \to \{1, \ldots, p\}`` such that ``\phi(u) \neq \phi(v)`` whenever ``u, v`` are distance-``k`` neighbors. * ``k``*-chromatic number* ``\xi_k(G)`` : minimum ``p`` such that ``\exists`` distance-``k`` coloring with ``p`` colors. * Distance-``k`` coloring problem : Find distance-``k`` coloring with fewest colors. * For every fixed integer ``k \ge 1``, the distance-``k`` graph coloring problem [is NP-hard](https://doi.org/10.1137/S089548019120016X). See [Section 2.1, 2.2, 3.2 of What color is your Jacobian ?](https://epubs.siam.org/doi/10.1137/S0036144504444711) """$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166metadatadisabled©show_logsîskip_as_script§cell_id$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166code_foldedäcodeGviz(args...; kws...) = three_columns(colored_plots(args...; kws...)...)$dc23180e-2b0f-41ae-aebf-0159a8f8677ametadatadisabled©show_logsîskip_as_script§cell_id$dc23180e-2b0f-41ae-aebf-0159a8f8677acode_foldedäcodeltwo_columns( md""" Consider the ``4 \times 5`` sparse matrix on the right: * Forward mode would require 5 JVP as there are 5 columns * Reverse mode would require 4 VJP as there are 4 rows Can we do better using the known sparsity pattern ? """, img("https://iclr-blogposts.github.io/2025/assets/img/2025-04-28-sparse-autodiff/sparse_map.svg", :width => 200), )$9df9c76a-48af-4ca6-83f1-b8798d6d4e34metadatadisabled©show_logsîskip_as_script§cell_id$9df9c76a-48af-4ca6-83f1-b8798d6d4e34code_folded¤code+Base.:/(a::MyGradientTracer, b::Number) = a$aeb8b749-006a-400f-9b7d-05333fd7214fmetadatadisabled©show_logsîskip_as_script§cell_id$aeb8b749-006a-400f-9b7d-05333fd7214fcode_foldedäcode%md"## Whole Jacobian in just two JVP"$f29078e8-242a-4b88-881f-781829c16ed5metadatadisabled©show_logsîskip_as_script§cell_id$f29078e8-242a-4b88-881f-781829c16ed5code_foldedäcodeْmd"Taken from a tutorial of the [SparseMatrixColorings' doc](https://gdalle.github.io/SparseMatrixColorings.jl/stable/tutorial/#Coloring-results)"$b33bf212-5f88-47ab-ba10-a2815d17f235metadatadisabled©show_logsîskip_as_script§cell_id$b33bf212-5f88-47ab-ba10-a2815d17f235code_foldedäcode1md""" With star coloring, we need at least 3 colors. With 2 colors, our two forward tangents are ```math D^\top = \begin{bmatrix} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 \end{bmatrix} \qquad\qquad\qquad AD = \begin{bmatrix} a_1 & a_2\\ a_2 + a_4 & a_3\\ a_5 & a_4 + a_6\\ a_6 & a_7 \end{bmatrix} ``` """$76162106-fb90-4883-b2d2-b87e1419c072metadatadisabled©show_logsîskip_as_script§cell_id$76162106-fb90-4883-b2d2-b87e1419c072code_foldedäcode,md""" ## Formulation as coloring problem """$12ffe7c2-2bf6-4949-ae28-f3d8e03a5da5metadatadisabled©show_logsîskip_as_script§cell_id$12ffe7c2-2bf6-4949-ae28-f3d8e03a5da5code_foldedäcodeZtwo_columns( md"Color's columns are structurally orthogonal", md"Jacobian from 3 JVP", )$97c94c5a-fab5-4226-b803-10c85a298f2ametadatadisabled©show_logsîskip_as_script§cell_id$97c94c5a-fab5-4226-b803-10c85a298f2acode_folded¤code2struct MyGradientTracer indexset::Set{Int} end$e882ebee-36ad-43d9-8ab7-20f7e8b2d9femetadatadisabled©show_logsîskip_as_script§cell_id$e882ebee-36ad-43d9-8ab7-20f7e8b2d9fecode_foldedäcodeUmd""" ## Example Consider the following sparsity pattern of the Jacobian matrix: """$3e6fc4af-19f4-4ff9-b9cf-759e831ff2a4metadatadisabled©show_logsîskip_as_script§cell_id$3e6fc4af-19f4-4ff9-b9cf-759e831ff2a4code_foldedäcodesviz(SparseMatrixColorings.what_fig_41().A, decompression = :direct, structure = :symmetric, plot_size = (5cm, 5cm))$0445aae6-2f7e-42b8-b30b-f31298cdeed0metadatadisabled©show_logsîskip_as_script§cell_id$0445aae6-2f7e-42b8-b30b-f31298cdeed0code_foldedäcodeFmd"`n` = $(@bind star_n Slider(3:10, default = 5, show_value = true))"$e721600c-1887-4e99-b474-a427b665e591metadatadisabled©show_logsîskip_as_script§cell_id$e721600c-1887-4e99-b474-a427b665e591code_foldedäcodeqa(md"What are the nonzero entries of ``i``th row of ``B_{\phi(i)}`` ?", md""" It contains ``A_{ii}`` but can it contain other nonzero entries ? Suppose that ``A_{ij}`` is nonzero with ``\phi(j) = \phi(i)``. This would mean that ``i`` and ``j`` are adjacent and of same color which contradicts the fact that ``\phi`` is a distance-1 coloring. So the only nonzero entry of the ``i``th row of ``B_{\phi(i)}`` is ``A_{ii}``. """)$91226321-fc72-4bd9-8d78-9c2bff5c760ametadatadisabled©show_logsîskip_as_script§cell_id$91226321-fc72-4bd9-8d78-9c2bff5c760acode_foldedäcodeRviz(S, structure = :nonsymmetric, decompression = :direct, plot_size = (3cm, 3cm))$8e2045f3-ee09-4439-b504-d2ca9f58a3ddmetadatadisabled©show_logsîskip_as_script§cell_id$8e2045f3-ee09-4439-b504-d2ca9f58a3ddcode_folded¤codecBase.:+(a::MyGradientTracer, b::MyGradientTracer) = MyGradientTracer(union(a.indexset, b.indexset))$95d7e9cd-b4a1-4205-b7d4-8c10916be8a2metadatadisabled©show_logsîskip_as_script§cell_id$95d7e9cd-b4a1-4205-b7d4-8c10916be8a2code_foldedäcodeٱstar = let I = collect(1:star_n) J = ones(Int, star_n) for i in 2:star_n push!(I, 1) push!(J, i) push!(I, i) push!(J, i) end sparse(I, J, ones(Int, length(I))) end;$a7b85908-404b-475b-9875-c1190de5ff71metadatadisabled©show_logsîskip_as_script§cell_id$a7b85908-404b-475b-9875-c1190de5ff71code_foldedäcode}md""" [**Definition 4.2**](https://epubs.siam.org/doi/10.1137/S0036144504444711) A coloring of the columns of a symmetric matrix ``A`` is *symmetrically orthogonal* if for every nonzero element ``a_{uv}``, either (1) there is no other column of color ``\phi(u)`` with a nonzero in row ``r_u``, or (2) there is no other column of color ``\phi(v)`` with a nonzero in row ``r_v``. """$22c1030b-bef5-4af5-9d5f-6afb4a7ae699metadatadisabled©show_logsîskip_as_script§cell_id$22c1030b-bef5-4af5-9d5f-6afb4a7ae699code_foldedäcode!img("Gebremedhin_Figure_6_1_mat")$a7e8569e-2fed-4069-aa84-ced67849ab15metadatadisabled©show_logsîskip_as_script§cell_id$a7e8569e-2fed-4069-aa84-ced67849ab15code_foldedäcode'md"## The same applies to reverse mode"$fa2a8104-2a3f-438c-bc63-4236a9f5ebebmetadatadisabled©show_logsîskip_as_script§cell_id$fa2a8104-2a3f-438c-bc63-4236a9f5ebebcode_folded¤codecBase.:*(a::MyGradientTracer, b::MyGradientTracer) = MyGradientTracer(union(a.indexset, b.indexset))$dbef0e7d-b731-4d83-98e3-104b23f26042metadatadisabled©show_logsîskip_as_script§cell_id$dbef0e7d-b731-4d83-98e3-104b23f26042code_foldedäcodeCmd"`n` = $(@bind n Slider(10:20, show_value = true, default = 16))"$a5769449-96cd-477a-bceb-ad9439a37430metadatadisabled©show_logsîskip_as_script§cell_id$a5769449-96cd-477a-bceb-ad9439a37430code_foldedäcodemd""" # What color is your Jacobian ? Given a sparse matrix ``A``, two graphs represent its sparsity: * Column intersection graph, used in [Software for estimating sparse Jacobian matrices, 1984](https://dl.acm.org/doi/abs/10.1145/1271.1610) * Bipartite graph, used in [Colpack](https://github.com/CSCsw/ColPack) and [SparseMatrixColoring](https://github.com/gdalle/SparseMatrixColorings.jl) $(img("Gebremedhin_Figure_3_1")) See [Section 3.4 of What color is your Jacobian ?](https://epubs.siam.org/doi/10.1137/S0036144504444711) """$6bd04f2f-ed5f-4ecf-91dd-8868ec5b83e1metadatadisabled©show_logsîskip_as_script§cell_id$6bd04f2f-ed5f-4ecf-91dd-8868ec5b83e1code_folded¤code1using SparseArrays, Images, SparseMatrixColorings$f8e9d672-e6ad-4910-8307-2b56616b11bcmetadatadisabled©show_logsîskip_as_script§cell_id$f8e9d672-e6ad-4910-8307-2b56616b11bccode_folded¤codeQBase.sign(x::MyGradientTracer) = MyGradientTracer(Set()) # return empty index set$7fec005c-11b9-4a75-a93c-195d456db190metadatadisabled©show_logsîskip_as_script§cell_id$7fec005c-11b9-4a75-a93c-195d456db190code_foldedäcodemd"## Scalar example"$6c174bac-faef-424a-9de7-e4c7be8ddb27metadatadisabled©show_logsîskip_as_script§cell_id$6c174bac-faef-424a-9de7-e4c7be8ddb27code_foldedäcode0md"## Larger example : star vs acyclic coloring"$b9dc524d-6c0b-4507-842c-b4b6cc90fd96metadatadisabled©show_logsîskip_as_script§cell_id$b9dc524d-6c0b-4507-842c-b4b6cc90fd96code_foldedäcodeqa(md"Is a coloring of the columns is distance-2 in the adjacency graph iff columns of the same color are structurally orthogonal ?", md""" The adjacency graph ``G`` is the quotient graph of the bipartite graph, say ``B``, under the identification ``r_i \sim a_i`` for all ``i``. If the diagonal entries of ``A`` are nonzero, for distance-1 neighbors ``a_u r_v`` of ``B``, we have a distance-2 neighbor ``a_ua_v`` of ``B`` (with the path ``a_ur_v, r_v a_v``). So two nodes are distance-2 neighbors in ``G`` iff they are distance-2 neighbors in ``B``. As a consequence, the statement is true **if the diagonal entries of ``A`` are nonzero. If diagonal entries of ``A`` are allowed to be zero, there is the following counter example where both columns are structurally orthogonal even though they are distance 1 neighbors (and hence also distance 2 neighbors). ```math \begin{bmatrix}\cdot & 1\\1 & \cdot\end{bmatrix} ``` """ )$70296870-49af-4564-bdb7-bd2d49f9114bmetadatadisabled©show_logsîskip_as_script§cell_id$70296870-49af-4564-bdb7-bd2d49f9114bcode_foldedäcodeRviz(star, decompression = :direct, structure = :symmetric, plot_size = (5cm, 5cm))$0a91e27f-3cea-415e-aed4-123482da375ametadatadisabled©show_logsîskip_as_script§cell_id$0a91e27f-3cea-415e-aed4-123482da375acode_foldedäcodemd"Simple [operator overloading implementation](https://adrianhill.de/SparseConnectivityTracer.jl/dev/internals/how_it_works/)"$2bd9ea13-362e-47ac-b26d-8e36d33e04eametadatadisabled©show_logsîskip_as_script§cell_id$2bd9ea13-362e-47ac-b26d-8e36d33e04eacode_foldedäcode٤md"For each color ``c``, we consider the submatrix ``B_c = A_{:,I}`` where ``I = \{i \mid \phi(i) = c\}`` is the set of columns corresponding to color-``c`` nodes."$cabeb42c-f40b-4549-b9a2-3bda7a988672metadatadisabled©show_logsîskip_as_script§cell_id$cabeb42c-f40b-4549-b9a2-3bda7a988672code_foldedäcodeimg("Gebremedhin_Figure_6_1")last_hot_reload_time cell_dependencies W$e3ae5697-6b0b-4d5f-99a0-d579b6eff655precedence_heuristic cell_id$e3ae5697-6b0b-4d5f-99a0-d579b6eff655downstream_cells_mapupstream_cells_map@md_strgetindex$a546edb2-6a72-4c5f-95f7-cc7709bbb505precedence_heuristic cell_id$a546edb2-6a72-4c5f-95f7-cc7709bbb505downstream_cells_mapupstream_cells_mapxtracer$2e3cdd4b-9d04-477c-8c6a-fec6ec846919F$a3bf5961-323b-4adc-99a0-9a456a0bfd48$d5b7f51b-e451-40a7-aa41-a8006decba33precedence_heuristic cell_id$d5b7f51b-e451-40a7-aa41-a8006decba33downstream_cells_mapupstream_cells_map@md_strgetindex$5892dfbb-b375-407b-a0a7-da66adb71b67precedence_heuristic cell_id$5892dfbb-b375-407b-a0a7-da66adb71b67downstream_cells_mapupstream_cells_map@md_strgetindex$1f02fda8-6b22-429e-9ef4-243e97372526precedence_heuristic cell_id$1f02fda8-6b22-429e-9ef4-243e97372526downstream_cells_mapupstream_cells_mapqa$dfe3dffd-926b-4083-9e66-8536e5df198d@md_strgetindex$1167ae71-b63d-4ccc-a120-31c8483eca85precedence_heuristic cell_id$1167ae71-b63d-4ccc-a120-31c8483eca85downstream_cells_mapytracerupstream_cells_mapf$d46dcdb3-ac4c-4ba9-ac48-6d6a693630d3xtracer$2e3cdd4b-9d04-477c-8c6a-fec6ec846919$45f4edeb-d934-413f-9f45-568465111b6eprecedence_heuristic cell_id$45f4edeb-d934-413f-9f45-568465111b6edownstream_cells_mapupstream_cells_map@md_strgetindex$a413c12c-72c1-4f46-b7f2-0b0118c1b232precedence_heuristic cell_id$a413c12c-72c1-4f46-b7f2-0b0118c1b232downstream_cells_mapupstream_cells_mapviz$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166cm*large$2fe7f4eb-ca33-4338-ba8e-29b769b0dcce$60070a94-d9ca-474b-9c6f-37468e3f030dprecedence_heuristic cell_id$60070a94-d9ca-474b-9c6f-37468e3f030ddownstream_cells_mapupstream_cells_mapqa$dfe3dffd-926b-4083-9e66-8536e5df198d@md_strgetindex$15cf368c-cada-4a72-b59b-a0f9dd0115b4precedence_heuristic cell_id$15cf368c-cada-4a72-b59b-a0f9dd0115b4downstream_cells_mapupstream_cells_mapqa$dfe3dffd-926b-4083-9e66-8536e5df198d@md_strgetindex$2fe7f4eb-ca33-4338-ba8e-29b769b0dcceprecedence_heuristic cell_id$2fe7f4eb-ca33-4338-ba8e-29b769b0dccedownstream_cells_maplarge$a413c12c-72c1-4f46-b7f2-0b0118c1b232$9b427766-5290-4dee-8dd5-5aab20080d0aupstream_cells_mapStableRNGn$dbef0e7d-b731-4d83-98e3-104b23f26042sparseI+BoolsprandSymmetric$a3bf5961-323b-4adc-99a0-9a456a0bfd48precedence_heuristic cell_id$a3bf5961-323b-4adc-99a0-9a456a0bfd48downstream_cells_mapF$a546edb2-6a72-4c5f-95f7-cc7709bbb505upstream_cells_map/+sign*$44a6b427-bd4b-4fa1-95d8-a8ea55719192precedence_heuristic cell_id$44a6b427-bd4b-4fa1-95d8-a8ea55719192downstream_cells_mapupstream_cells_mapqa$dfe3dffd-926b-4083-9e66-8536e5df198d@md_strgetindex$9e24f674-42af-4fa8-bf3e-42e14d855a58precedence_heuristic cell_id$9e24f674-42af-4fa8-bf3e-42e14d855a58downstream_cells_mapupstream_cells_mapimg$2728dc2c-ca17-4989-9259-451f95a24bd2@md_strgetindex=>two_columns$e820e135-2df2-4fa3-a09b-8ce7e5a1f745$39e06fde-d734-11f0-a308-89fba7e8abd6precedence_heuristic cell_id$39e06fde-d734-11f0-a308-89fba7e8abd6downstream_cells_mapupstream_cells_mapHypertextLiteral$75597493-3e69-437f-9408-b43a89b35559HypertextLiteral.content$PlutoTeachingTools.ChooseDisplayModeHypertextLiteral.Result@htlPlutoUI.TableOfContentsPlutoUI$75597493-3e69-437f-9408-b43a89b35559PlutoTeachingTools$75597493-3e69-437f-9408-b43a89b35559HypertextLiteral.Bypass$21898d8d-f822-4128-ad56-d9a10865fb1dprecedence_heuristic cell_id$21898d8d-f822-4128-ad56-d9a10865fb1ddownstream_cells_mapthree_columns$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166upstream_cells_mapBasehbox@html_strDiv=>DictBase.Docs.HTML$4f8de444-dcb4-411a-b087-6948699614e0precedence_heuristiccell_id$4f8de444-dcb4-411a-b087-6948699614e0downstream_cells_mapLinearAlgebraGraphs$e9135060-75d4-4f5a-9315-2e5fbb493cdfGraphPlotStableRNGsupstream_cells_map$75597493-3e69-437f-9408-b43a89b35559precedence_heuristiccell_id$75597493-3e69-437f-9408-b43a89b35559downstream_cells_mapHypertextLiteral$39e06fde-d734-11f0-a308-89fba7e8abd6$2728dc2c-ca17-4989-9259-451f95a24bd2$dfe3dffd-926b-4083-9e66-8536e5df198dPlutoUI$39e06fde-d734-11f0-a308-89fba7e8abd6$2728dc2c-ca17-4989-9259-451f95a24bd2ExperimentalLayoutPlutoTeachingTools$39e06fde-d734-11f0-a308-89fba7e8abd6$2728dc2c-ca17-4989-9259-451f95a24bd2upstream_cells_map$9b427766-5290-4dee-8dd5-5aab20080d0aprecedence_heuristic cell_id$9b427766-5290-4dee-8dd5-5aab20080d0adownstream_cells_mapupstream_cells_mapviz$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166cm*large$2fe7f4eb-ca33-4338-ba8e-29b769b0dcce$2578b84a-365a-47b6-b58f-1696517c5d02precedence_heuristic cell_id$2578b84a-365a-47b6-b58f-1696517c5d02downstream_cells_mapupstream_cells_map@md_strgetindex$dfe3dffd-926b-4083-9e66-8536e5df198dprecedence_heuristic cell_id$dfe3dffd-926b-4083-9e66-8536e5df198ddownstream_cells_mapqa$b9dc524d-6c0b-4507-842c-b4b6cc90fd96$1f02fda8-6b22-429e-9ef4-243e97372526$592510fd-a0e4-42e5-ae5b-cac301e74f0a$26191290-2b2d-43fe-b2bf-d690fd0bbe15$60070a94-d9ca-474b-9c6f-37468e3f030d$04ea8b79-63ba-4eb4-938c-98a21668924a$e721600c-1887-4e99-b474-a427b665e591$44a6b427-bd4b-4fa1-95d8-a8ea55719192$15cf368c-cada-4a72-b59b-a0f9dd0115b4$79910840-ec59-4433-bfb3-ae2d8da40d22_inline_htmlupstream_cells_mapHypertextLiteral$75597493-3e69-437f-9408-b43a89b35559HypertextLiteral.content@htlHypertextLiteral.ResultMarkdownsprintHTMLHypertextLiteral.Bypass$18594f1f-6036-4a95-8682-cf415c998311precedence_heuristic cell_id$18594f1f-6036-4a95-8682-cf415c998311downstream_cells_mapupstream_cells_map@md_strgetindex$e2eb1894-06ad-47a0-9ee0-c65b24a669b5precedence_heuristic cell_id$e2eb1894-06ad-47a0-9ee0-c65b24a669b5downstream_cells_mapupstream_cells_map@md_strgetindex$32440932-322a-46ce-911d-5fa6a1136bcaprecedence_heuristic cell_id$32440932-322a-46ce-911d-5fa6a1136bcadownstream_cells_mapijkl$33b368e7-d71e-40ff-8170-a18d11db98fc$647c372e-c094-4dfc-8a48-7b7f93fb94ddupstream_cells_mapsparse$c2e4982a-3798-4c45-8831-5a76b3b29f6eprecedence_heuristic cell_id$c2e4982a-3798-4c45-8831-5a76b3b29f6edownstream_cells_mapupstream_cells_map@md_strgetindex$79910840-ec59-4433-bfb3-ae2d8da40d22precedence_heuristic cell_id$79910840-ec59-4433-bfb3-ae2d8da40d22downstream_cells_mapupstream_cells_mapqa$dfe3dffd-926b-4083-9e66-8536e5df198d@md_strgetindex$5a6aec48-54fb-4d88-a8a1-b06a2bb99108precedence_heuristic cell_id$5a6aec48-54fb-4d88-a8a1-b06a2bb99108downstream_cells_mapS$91226321-fc72-4bd9-8d78-9c2bff5c760aupstream_cells_mapsparse$726208c6-e856-42a2-b027-555388bc505eprecedence_heuristic cell_id$726208c6-e856-42a2-b027-555388bc505edownstream_cells_mapupstream_cells_mapimg$2728dc2c-ca17-4989-9259-451f95a24bd2two_columns$e820e135-2df2-4fa3-a09b-8ce7e5a1f745$b18a3bf6-102e-49f5-af8c-f1c35d2e2a8bprecedence_heuristic cell_id$b18a3bf6-102e-49f5-af8c-f1c35d2e2a8bdownstream_cells_mapupstream_cells_map@md_strgetindex$352c92ec-14da-4beb-85c4-f66d77fa42d6precedence_heuristic cell_id$352c92ec-14da-4beb-85c4-f66d77fa42d6downstream_cells_mapupstream_cells_mapimg$2728dc2c-ca17-4989-9259-451f95a24bd2=>$647c372e-c094-4dfc-8a48-7b7f93fb94ddprecedence_heuristic cell_id$647c372e-c094-4dfc-8a48-7b7f93fb94dddownstream_cells_mapupstream_cells_mapviz$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166cm*ijkl$32440932-322a-46ce-911d-5fa6a1136bca$4da92dbb-fcbd-4991-a2f1-f866778a27efprecedence_heuristic cell_id$4da92dbb-fcbd-4991-a2f1-f866778a27efdownstream_cells_mapupstream_cells_map@md_strgetindex$e820e135-2df2-4fa3-a09b-8ce7e5a1f745precedence_heuristic cell_id$e820e135-2df2-4fa3-a09b-8ce7e5a1f745downstream_cells_maptwo_columns$dc23180e-2b0f-41ae-aebf-0159a8f8677a$9e24f674-42af-4fa8-bf3e-42e14d855a58$a01688ec-8f16-4d39-b39d-6d1acd24d7ad$726208c6-e856-42a2-b027-555388bc505e$12ffe7c2-2bf6-4949-ae28-f3d8e03a5da5upstream_cells_mapBasehbox@html_strDiv=>DictBase.Docs.HTML$1efb0f40-fb9e-4e5b-be59-84910afbf376precedence_heuristic cell_id$1efb0f40-fb9e-4e5b-be59-84910afbf376downstream_cells_mapupstream_cells_map@md_strgetindex$2728dc2c-ca17-4989-9259-451f95a24bd2precedence_heuristic cell_id$2728dc2c-ca17-4989-9259-451f95a24bd2downstream_cells_mapimg$dc23180e-2b0f-41ae-aebf-0159a8f8677a$9e24f674-42af-4fa8-bf3e-42e14d855a58$a01688ec-8f16-4d39-b39d-6d1acd24d7ad$726208c6-e856-42a2-b027-555388bc505e$352c92ec-14da-4beb-85c4-f66d77fa42d6$a5769449-96cd-477a-bceb-ad9439a37430$cabeb42c-f40b-4549-b9a2-3bda7a988672$22c1030b-bef5-4af5-9d5f-6afb4a7ae699URL$2728dc2c-ca17-4989-9259-451f95a24bd2save_imageimgpathPath$2728dc2c-ca17-4989-9259-451f95a24bd2upstream_cells_map HypertextLiteral$75597493-3e69-437f-9408-b43a89b35559HypertextLiteral.contentStringHypertextLiteral.Result@htlPlutoUI.LocalResourcePlutoUI$75597493-3e69-437f-9408-b43a89b35559URL$2728dc2c-ca17-4989-9259-451f95a24bd2joinpath!HypertextLiteral.BypassHypertextLiteral.attribute_pairinstartswith&PlutoTeachingTools.RobustLocalResourcesplit@__DIR__Path$2728dc2c-ca17-4989-9259-451f95a24bd2*PlutoTeachingTools$75597493-3e69-437f-9408-b43a89b35559$33b368e7-d71e-40ff-8170-a18d11db98fcprecedence_heuristic cell_id$33b368e7-d71e-40ff-8170-a18d11db98fcdownstream_cells_mapupstream_cells_mapviz$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166cm*ijkl$32440932-322a-46ce-911d-5fa6a1136bca$29d9f355-26aa-4714-9f9e-3d020016662eprecedence_heuristic cell_id$29d9f355-26aa-4714-9f9e-3d020016662edownstream_cells_mapupstream_cells_map@md_strgetindex$e9135060-75d4-4f5a-9315-2e5fbb493cdfprecedence_heuristic cell_id$e9135060-75d4-4f5a-9315-2e5fbb493cdfdownstream_cells_mapcolored_plots$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166upstream_cells_map Diagonalscale$d23e7238-5edb-42d3-96d9-0dffa9e7f326coloring$SparseMatrixColorings.AdjacencyGraphSparseMatrixColorings$6bd04f2f-ed5f-4ecf-91dd-8868ec5b83e1Graphs.nv-diagadjointRGBARGBGreedyColoringAlgorithmncolors!SparseMatrixColorings.show_colorsconvert:ColoringProblemborder$d23e7238-5edb-42d3-96d9-0dffa9e7f326Graphs$4f8de444-dcb4-411a-b087-6948699614e0conj==Graphs.SimpleDiGraphpad$d23e7238-5edb-42d3-96d9-0dffa9e7f326distinguishable_colors*gplot$a4ecf92d-6c45-4112-8f0c-06a6d227cd84precedence_heuristic cell_id$a4ecf92d-6c45-4112-8f0c-06a6d227cd84downstream_cells_mapupstream_cells_map@md_strgetindex$592510fd-a0e4-42e5-ae5b-cac301e74f0aprecedence_heuristic cell_id$592510fd-a0e4-42e5-ae5b-cac301e74f0adownstream_cells_mapupstream_cells_mapqa$dfe3dffd-926b-4083-9e66-8536e5df198d@md_strgetindex$d46dcdb3-ac4c-4ba9-ac48-6d6a693630d3precedence_heuristic cell_id$d46dcdb3-ac4c-4ba9-ac48-6d6a693630d3downstream_cells_mapf$1167ae71-b63d-4ccc-a120-31c8483eca85upstream_cells_map+sign*$760ef943-e9d9-4cdc-8977-932cf6fcb78aprecedence_heuristic cell_id$760ef943-e9d9-4cdc-8977-932cf6fcb78adownstream_cells_mapupstream_cells_map@md_strgetindex$2e3cdd4b-9d04-477c-8c6a-fec6ec846919precedence_heuristic cell_id$2e3cdd4b-9d04-477c-8c6a-fec6ec846919downstream_cells_mapxtracer$1167ae71-b63d-4ccc-a120-31c8483eca85$a546edb2-6a72-4c5f-95f7-cc7709bbb505upstream_cells_mapSetMyGradientTracer$97c94c5a-fab5-4226-b803-10c85a298f2a$4ab46ef8-0f6e-4e6d-8f6f-ac466977b476precedence_heuristic cell_id$4ab46ef8-0f6e-4e6d-8f6f-ac466977b476downstream_cells_mapupstream_cells_map@md_strgetindex$19dd6563-1a4e-479f-881d-9bcbc720ea36precedence_heuristic cell_id$19dd6563-1a4e-479f-881d-9bcbc720ea36downstream_cells_mapupstream_cells_map@md_strgetindex$26191290-2b2d-43fe-b2bf-d690fd0bbe15precedence_heuristic cell_id$26191290-2b2d-43fe-b2bf-d690fd0bbe15downstream_cells_mapupstream_cells_mapqa$dfe3dffd-926b-4083-9e66-8536e5df198d@md_strgetindex$04ea8b79-63ba-4eb4-938c-98a21668924aprecedence_heuristic cell_id$04ea8b79-63ba-4eb4-938c-98a21668924adownstream_cells_mapupstream_cells_mapqa$dfe3dffd-926b-4083-9e66-8536e5df198d@md_strgetindex$874b6593-7310-4788-beb0-2f18c0ca09a7precedence_heuristic cell_id$874b6593-7310-4788-beb0-2f18c0ca09a7downstream_cells_mapupstream_cells_map@md_strgetindex$e3dec4ca-69c0-4955-9303-5f8a239546f2precedence_heuristic cell_id$e3dec4ca-69c0-4955-9303-5f8a239546f2downstream_cells_mapupstream_cells_map@md_strgetindex$e6697119-2801-48e2-b978-facc00af636dprecedence_heuristic cell_id$e6697119-2801-48e2-b978-facc00af636ddownstream_cells_mapupstream_cells_map@md_strgetindex$f2418632-3261-4acb-8cc6-df333b5480a5precedence_heuristic cell_id$f2418632-3261-4acb-8cc6-df333b5480a5downstream_cells_mapupstream_cells_map@md_strgetindex$d23e7238-5edb-42d3-96d9-0dffa9e7f326precedence_heuristic cell_id$d23e7238-5edb-42d3-96d9-0dffa9e7f326downstream_cells_mapscale$e9135060-75d4-4f5a-9315-2e5fbb493cdfpad$e9135060-75d4-4f5a-9315-2e5fbb493cdfborder$e9135060-75d4-4f5a-9315-2e5fbb493cdfupstream_cells_map:PlutoRunnerCore.applicableCoreBasehboxBase.get@md_strgetindexSlider@bindPlutoRunner.create_bond$285d3797-5086-4adc-839c-2204128585e1precedence_heuristic cell_id$285d3797-5086-4adc-839c-2204128585e1downstream_cells_mapupstream_cells_map@md_strgetindex$a01688ec-8f16-4d39-b39d-6d1acd24d7adprecedence_heuristic cell_id$a01688ec-8f16-4d39-b39d-6d1acd24d7addownstream_cells_mapupstream_cells_mapimg$2728dc2c-ca17-4989-9259-451f95a24bd2=>two_columns$e820e135-2df2-4fa3-a09b-8ce7e5a1f745$d0ba0c62-c788-4871-959c-fe7044519849precedence_heuristic cell_id$d0ba0c62-c788-4871-959c-fe7044519849downstream_cells_mapupstream_cells_map@md_strgetindex$1617c79d-3abe-4ffc-9ee1-3312f2b28eb5precedence_heuristic cell_id$1617c79d-3abe-4ffc-9ee1-3312f2b28eb5downstream_cells_mapupstream_cells_map@md_strgetindex$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166precedence_heuristic cell_id$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166downstream_cells_mapviz$91226321-fc72-4bd9-8d78-9c2bff5c760a$33b368e7-d71e-40ff-8170-a18d11db98fc$70296870-49af-4564-bdb7-bd2d49f9114b$3e6fc4af-19f4-4ff9-b9cf-759e831ff2a4$647c372e-c094-4dfc-8a48-7b7f93fb94dd$a413c12c-72c1-4f46-b7f2-0b0118c1b232$9b427766-5290-4dee-8dd5-5aab20080d0aupstream_cells_mapcolored_plots$e9135060-75d4-4f5a-9315-2e5fbb493cdfthree_columns$21898d8d-f822-4128-ad56-d9a10865fb1d$dc23180e-2b0f-41ae-aebf-0159a8f8677aprecedence_heuristic cell_id$dc23180e-2b0f-41ae-aebf-0159a8f8677adownstream_cells_mapupstream_cells_mapimg$2728dc2c-ca17-4989-9259-451f95a24bd2@md_strgetindex=>two_columns$e820e135-2df2-4fa3-a09b-8ce7e5a1f745$9df9c76a-48af-4ca6-83f1-b8798d6d4e34precedence_heuristic cell_id$9df9c76a-48af-4ca6-83f1-b8798d6d4e34downstream_cells_mapBase./upstream_cells_mapBaseMyGradientTracer$97c94c5a-fab5-4226-b803-10c85a298f2aNumber$aeb8b749-006a-400f-9b7d-05333fd7214fprecedence_heuristic cell_id$aeb8b749-006a-400f-9b7d-05333fd7214fdownstream_cells_mapupstream_cells_map@md_strgetindex$f29078e8-242a-4b88-881f-781829c16ed5precedence_heuristic cell_id$f29078e8-242a-4b88-881f-781829c16ed5downstream_cells_mapupstream_cells_map@md_strgetindex$b33bf212-5f88-47ab-ba10-a2815d17f235precedence_heuristic cell_id$b33bf212-5f88-47ab-ba10-a2815d17f235downstream_cells_mapupstream_cells_map@md_strgetindex$76162106-fb90-4883-b2d2-b87e1419c072precedence_heuristic cell_id$76162106-fb90-4883-b2d2-b87e1419c072downstream_cells_mapupstream_cells_map@md_strgetindex$12ffe7c2-2bf6-4949-ae28-f3d8e03a5da5precedence_heuristic cell_id$12ffe7c2-2bf6-4949-ae28-f3d8e03a5da5downstream_cells_mapupstream_cells_map@md_strgetindextwo_columns$e820e135-2df2-4fa3-a09b-8ce7e5a1f745$97c94c5a-fab5-4226-b803-10c85a298f2aprecedence_heuristic cell_id$97c94c5a-fab5-4226-b803-10c85a298f2adownstream_cells_mapMyGradientTracer$8e2045f3-ee09-4439-b504-d2ca9f58a3dd$fa2a8104-2a3f-438c-bc63-4236a9f5ebeb$9df9c76a-48af-4ca6-83f1-b8798d6d4e34$f8e9d672-e6ad-4910-8307-2b56616b11bc$2e3cdd4b-9d04-477c-8c6a-fec6ec846919upstream_cells_mapIntSet$e882ebee-36ad-43d9-8ab7-20f7e8b2d9feprecedence_heuristic cell_id$e882ebee-36ad-43d9-8ab7-20f7e8b2d9fedownstream_cells_mapupstream_cells_map@md_strgetindex$3e6fc4af-19f4-4ff9-b9cf-759e831ff2a4precedence_heuristic cell_id$3e6fc4af-19f4-4ff9-b9cf-759e831ff2a4downstream_cells_mapupstream_cells_map!SparseMatrixColorings.what_fig_41SparseMatrixColorings$6bd04f2f-ed5f-4ecf-91dd-8868ec5b83e1viz$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166cm*$0445aae6-2f7e-42b8-b30b-f31298cdeed0precedence_heuristic cell_id$0445aae6-2f7e-42b8-b30b-f31298cdeed0downstream_cells_mapstar_n$95d7e9cd-b4a1-4205-b7d4-8c10916be8a2upstream_cells_map:PlutoRunnerCore.applicableCoreBaseBase.get@md_strgetindexSlider@bindPlutoRunner.create_bond$e721600c-1887-4e99-b474-a427b665e591precedence_heuristic cell_id$e721600c-1887-4e99-b474-a427b665e591downstream_cells_mapupstream_cells_mapqa$dfe3dffd-926b-4083-9e66-8536e5df198d@md_strgetindex$91226321-fc72-4bd9-8d78-9c2bff5c760aprecedence_heuristic cell_id$91226321-fc72-4bd9-8d78-9c2bff5c760adownstream_cells_mapupstream_cells_mapviz$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166cmS$5a6aec48-54fb-4d88-a8a1-b06a2bb99108*$8e2045f3-ee09-4439-b504-d2ca9f58a3ddprecedence_heuristic cell_id$8e2045f3-ee09-4439-b504-d2ca9f58a3dddownstream_cells_mapBase.+upstream_cells_mapBaseunionMyGradientTracer$97c94c5a-fab5-4226-b803-10c85a298f2a$95d7e9cd-b4a1-4205-b7d4-8c10916be8a2precedence_heuristic cell_id$95d7e9cd-b4a1-4205-b7d4-8c10916be8a2downstream_cells_mapstar$70296870-49af-4564-bdb7-bd2d49f9114bupstream_cells_mappush!Intcollect:lengthsparsestar_n$0445aae6-2f7e-42b8-b30b-f31298cdeed0ones$a7b85908-404b-475b-9875-c1190de5ff71precedence_heuristic cell_id$a7b85908-404b-475b-9875-c1190de5ff71downstream_cells_mapupstream_cells_map@md_strgetindex$22c1030b-bef5-4af5-9d5f-6afb4a7ae699precedence_heuristic cell_id$22c1030b-bef5-4af5-9d5f-6afb4a7ae699downstream_cells_mapupstream_cells_mapimg$2728dc2c-ca17-4989-9259-451f95a24bd2$a7e8569e-2fed-4069-aa84-ced67849ab15precedence_heuristic cell_id$a7e8569e-2fed-4069-aa84-ced67849ab15downstream_cells_mapupstream_cells_map@md_strgetindex$fa2a8104-2a3f-438c-bc63-4236a9f5ebebprecedence_heuristic cell_id$fa2a8104-2a3f-438c-bc63-4236a9f5ebebdownstream_cells_mapBase.*upstream_cells_mapBaseunionMyGradientTracer$97c94c5a-fab5-4226-b803-10c85a298f2a$dbef0e7d-b731-4d83-98e3-104b23f26042precedence_heuristic cell_id$dbef0e7d-b731-4d83-98e3-104b23f26042downstream_cells_mapn$2fe7f4eb-ca33-4338-ba8e-29b769b0dcceupstream_cells_map:PlutoRunnerCore.applicableCoreBaseBase.get@md_strgetindexSlider@bindPlutoRunner.create_bond$a5769449-96cd-477a-bceb-ad9439a37430precedence_heuristic cell_id$a5769449-96cd-477a-bceb-ad9439a37430downstream_cells_mapupstream_cells_mapimg$2728dc2c-ca17-4989-9259-451f95a24bd2@md_strgetindex$6bd04f2f-ed5f-4ecf-91dd-8868ec5b83e1precedence_heuristiccell_id$6bd04f2f-ed5f-4ecf-91dd-8868ec5b83e1downstream_cells_mapSparseArraysSparseMatrixColorings$3e6fc4af-19f4-4ff9-b9cf-759e831ff2a4$e9135060-75d4-4f5a-9315-2e5fbb493cdfImagesupstream_cells_map$f8e9d672-e6ad-4910-8307-2b56616b11bcprecedence_heuristic cell_id$f8e9d672-e6ad-4910-8307-2b56616b11bcdownstream_cells_mapBase.signupstream_cells_mapBaseSetMyGradientTracer$97c94c5a-fab5-4226-b803-10c85a298f2a$7fec005c-11b9-4a75-a93c-195d456db190precedence_heuristic cell_id$7fec005c-11b9-4a75-a93c-195d456db190downstream_cells_mapupstream_cells_map@md_strgetindex$6c174bac-faef-424a-9de7-e4c7be8ddb27precedence_heuristic cell_id$6c174bac-faef-424a-9de7-e4c7be8ddb27downstream_cells_mapupstream_cells_map@md_strgetindex$b9dc524d-6c0b-4507-842c-b4b6cc90fd96precedence_heuristic cell_id$b9dc524d-6c0b-4507-842c-b4b6cc90fd96downstream_cells_mapupstream_cells_mapqa$dfe3dffd-926b-4083-9e66-8536e5df198d@md_strgetindex$70296870-49af-4564-bdb7-bd2d49f9114bprecedence_heuristic cell_id$70296870-49af-4564-bdb7-bd2d49f9114bdownstream_cells_mapupstream_cells_mapviz$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166star$95d7e9cd-b4a1-4205-b7d4-8c10916be8a2cm*$0a91e27f-3cea-415e-aed4-123482da375aprecedence_heuristic cell_id$0a91e27f-3cea-415e-aed4-123482da375adownstream_cells_mapupstream_cells_map@md_strgetindex$2bd9ea13-362e-47ac-b26d-8e36d33e04eaprecedence_heuristic cell_id$2bd9ea13-362e-47ac-b26d-8e36d33e04eadownstream_cells_mapupstream_cells_map@md_strgetindex$cabeb42c-f40b-4549-b9a2-3bda7a988672precedence_heuristic cell_id$cabeb42c-f40b-4549-b9a2-3bda7a988672downstream_cells_mapupstream_cells_mapimg$2728dc2c-ca17-4989-9259-451f95a24bd2shortpathsparse.jllast_save_timeAڸؗپnotebook_id$276c7d04-d3ab-11f1-88a1-8ff9776f78f0nbpkgbusy_packages,waiting_for_permission_but_probably_disabled§enabledðterminal_outputsHypertextLiteral [0m[1mWaiting for other notebooks to finish Pkg operations...[22m [90m===[39m [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[e37daf67] [39m[93m↑ LibGit2_jll v1.9.1+0 ⇒ v1.9.7+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[efcefdf7] [39m[93m↑ PCRE2_jll v10.46.0+0 ⇒ v10.47.0+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [90m[3f19e933] [39m[93m↑ p7zip_jll v17.8.2+0 ⇒ v17.8.3+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39mSparseMatrixColorings [0m[1mWaiting for other notebooks to finish Pkg operations...[22m [90m===[39m [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[e37daf67] [39m[93m↑ LibGit2_jll v1.9.1+0 ⇒ v1.9.7+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[efcefdf7] [39m[93m↑ PCRE2_jll v10.46.0+0 ⇒ v10.47.0+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [90m[3f19e933] [39m[93m↑ p7zip_jll v17.8.2+0 ⇒ v17.8.3+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39mGraphPlot [0m[1mWaiting for other notebooks to finish Pkg operations...[22m [90m===[39m [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[e37daf67] [39m[93m↑ LibGit2_jll v1.9.1+0 ⇒ v1.9.7+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[efcefdf7] [39m[93m↑ PCRE2_jll v10.46.0+0 ⇒ v10.47.0+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [90m[3f19e933] [39m[93m↑ p7zip_jll v17.8.2+0 ⇒ v17.8.3+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39mnbpkg_sync [0m[1mWaiting for other notebooks to finish Pkg operations...[22m [90m===[39m [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[e37daf67] [39m[93m↑ LibGit2_jll v1.9.1+0 ⇒ v1.9.7+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[efcefdf7] [39m[93m↑ PCRE2_jll v10.46.0+0 ⇒ v10.47.0+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [90m[3f19e933] [39m[93m↑ p7zip_jll v17.8.2+0 ⇒ v17.8.3+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39mImages [0m[1mWaiting for other notebooks to finish Pkg operations...[22m [90m===[39m [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[e37daf67] [39m[93m↑ LibGit2_jll v1.9.1+0 ⇒ v1.9.7+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[efcefdf7] [39m[93m↑ PCRE2_jll v10.46.0+0 ⇒ v10.47.0+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [90m[3f19e933] [39m[93m↑ p7zip_jll v17.8.2+0 ⇒ v17.8.3+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39mSparseArrays [0m[1mWaiting for other notebooks to finish Pkg operations...[22m [90m===[39m [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[e37daf67] [39m[93m↑ LibGit2_jll v1.9.1+0 ⇒ v1.9.7+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[efcefdf7] [39m[93m↑ PCRE2_jll v10.46.0+0 ⇒ v10.47.0+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [90m[3f19e933] [39m[93m↑ p7zip_jll v17.8.2+0 ⇒ v17.8.3+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39mPlutoUI [0m[1mWaiting for other notebooks to finish Pkg operations...[22m [90m===[39m [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[e37daf67] [39m[93m↑ LibGit2_jll v1.9.1+0 ⇒ v1.9.7+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[efcefdf7] [39m[93m↑ PCRE2_jll v10.46.0+0 ⇒ v10.47.0+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [90m[3f19e933] [39m[93m↑ p7zip_jll v17.8.2+0 ⇒ v17.8.3+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39mGraphs [0m[1mWaiting for other notebooks to finish Pkg operations...[22m [90m===[39m [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[e37daf67] [39m[93m↑ LibGit2_jll v1.9.1+0 ⇒ v1.9.7+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[efcefdf7] [39m[93m↑ PCRE2_jll v10.46.0+0 ⇒ v10.47.0+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [90m[3f19e933] [39m[93m↑ p7zip_jll v17.8.2+0 ⇒ v17.8.3+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39mLinearAlgebra [0m[1mWaiting for other notebooks to finish Pkg operations...[22m [90m===[39m [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[e37daf67] [39m[93m↑ LibGit2_jll v1.9.1+0 ⇒ v1.9.7+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[efcefdf7] [39m[93m↑ PCRE2_jll v10.46.0+0 ⇒ v10.47.0+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [90m[3f19e933] [39m[93m↑ p7zip_jll v17.8.2+0 ⇒ v17.8.3+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39mStableRNGs [0m[1mWaiting for other notebooks to finish Pkg operations...[22m [90m===[39m [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[e37daf67] [39m[93m↑ LibGit2_jll v1.9.1+0 ⇒ v1.9.7+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[efcefdf7] [39m[93m↑ PCRE2_jll v10.46.0+0 ⇒ v10.47.0+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [90m[3f19e933] [39m[93m↑ p7zip_jll v17.8.2+0 ⇒ v17.8.3+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39mPlutoTeachingTools [0m[1mWaiting for other notebooks to finish Pkg operations...[22m [90m===[39m [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_kwetrqbojw/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[e37daf67] [39m[93m↑ LibGit2_jll v1.9.1+0 ⇒ v1.9.7+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[efcefdf7] [39m[93m↑ PCRE2_jll v10.46.0+0 ⇒ v10.47.0+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [90m[3f19e933] [39m[93m↑ p7zip_jll v17.8.2+0 ⇒ v17.8.3+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39mwaiting_for_permission·restart_recommended_msgrestart_required_msginstalled_versionsHypertextLiteral1.0.0SparseArraysstdlibSparseMatrixColorings0.4.28PlutoUI0.7.83GraphPlot0.6.2!__internal_julia_manifest_version1.13.3StableRNGs1.0.4LinearAlgebrastdlibGraphs1.15.0__internal_julia_version1.13.3PlutoTeachingTools0.4.7Images0.26.2install_time_ns$[%instantiatedípluto_versionv1.1.0in_temp_dir