bondscell_resultsU$a5769449-96cd-477a-bceb-ad9439a37430queued¤logsrunning¦outputbody

What color is your Jacobian ?

Given a sparse matrix $A$, two graphs represent its sparsity:

See Section 3.4 of What color is your Jacobian ?

mimetext/htmlrootassigneelast_run_timestampAzr~persist_js_state·has_pluto_hook_features§cell_id$a5769449-96cd-477a-bceb-ad9439a37430depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$a4ecf92d-6c45-4112-8f0c-06a6d227cd84queued¤logsrunning¦outputbody

Star coloring

Definition 4.5 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 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.

mimetext/htmlrootassigneelast_run_timestampAzdpersist_js_state÷has_pluto_hook_features§cell_id$a4ecf92d-6c45-4112-8f0c-06a6d227cd84depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$f29078e8-242a-4b88-881f-781829c16ed5queued¤logsrunning¦outputbody

Taken from a tutorial of the SparseMatrixColorings' doc

mimetext/htmlrootassigneelast_run_timestampAzpersist_js_state÷has_pluto_hook_features§cell_id$f29078e8-242a-4b88-881f-781829c16ed5depends_on_disabled_cells§runtimeҵpublished_object_keysdepends_on_skipped_cells§errored$91226321-fc72-4bd9-8d78-9c2bff5c760aqueued¤logsrunning¦outputbodychildrenPNG  IHDRDVsRGBgAMA a cHRMz&u0`:pQ<5IDATxm[W}؁`*+b``xf`5f 0k+u{W]yhY`-ǕG:︮ysyk]y'_5f 0kY`5f 0kY`5[s5N^ v`5f< s5f]<9q}\ys;y' 0kY`5f 0kY`5f 0kY̚/:̹`5;ϝK`5y}W넯\'/f 0kYfg{]WNI`5f 0kY`5f 0kY`͜sNd 0kY̚w+:5f 0kY<]yF`\<9|q5f 0kY`5f 0kY`5y3 5y}'>5f 0)DIIENDB`image/pngchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+object1_ text/htmlchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+objectlPNG  IHDRlDsRGBgAMA a cHRMz&u0`:pQ<IDATxP~@㰘` }$@TIE"E*T(rlqŽ>"E*֋+|cWmť gHE"E*T(RQHE"E*T(RQHE"ENyنG3RQHEc3 0[kx0(RQIk7{qن$RQHE"E*T(RQHE"E*T(RQHEfv`7"E*aRQHE"E-5|`RQHEzqoJ IHE"E*T(RQHE"E*T(RQHE"'

Larger example : star vs acyclic coloring

mimetext/htmlrootassigneelast_run_timestampAzpersist_js_state÷has_pluto_hook_features§cell_id$6c174bac-faef-424a-9de7-e4c7be8ddb27depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$2728dc2c-ca17-4989-9259-451f95a24bd2queued¤logsrunning¦outputbody%img (generic function with 3 methods)mimetext/plainrootassigneelast_run_timestampAz:'1persist_js_state·has_pluto_hook_features§cell_id$2728dc2c-ca17-4989-9259-451f95a24bd2depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$a413c12c-72c1-4f46-b7f2-0b0118c1b232queued¤logsrunning¦outputbodychildrenPNG  IHDRsRGBgAMA a cHRMz&u0`:pQ<*IDATxmE};%s!Txw-\Ȁ 8'7 V!I IPHҀG6A4ۄf?6aP!I_~d_sF/>+7<[k?{oU^Y!I IPHҀB4$ ($i@!IIN\+KA==~0[4tTaq+4q5ۄi :6BɉsF m+B4$ ($i@!I IPHҀB8,A;*$i@q\8t[J$ ($i@i 6am15ۄ*$i@?~d[ܬ%]5˧qʑ4$ ($i@!I IPHҀB4%'%EW$ (;z8$ ($i@i 6AAMl)$i@?~d[ܬ%ܬnWVyg$ ($i@!I IPHҀB4$ (Gɉke қ.ܱU!I N^!\$ (&OM؟f4ۄfM!I~dY#Kؽ*A+:OWVyg$ ($i@!I IPHҀB4$ (.9qYa< {z/wlUHҀqTHҀBz/m¬fpl&L!I +ݏ*-}nvsCثB4$ ($i@!I IPHҀBzW%C4{!\/G8B44ۄcj l5A5˧qʑ4$ ($i@!I IPHҀB4%'t%A!I N$ ($i@O6ᘚmEMl.m15ۄA$ (vY{f,-ݏ*-}nޅX牛($i@!I IPHҀB4$ ($i@cY.k%'v!\+KwO4ا} ^؁B4QM5ۄY6&j THҀY#9K#k$'nsCxK5[k?rd$ ($i@!I IPHҀB4$ (~!9cJNCVϯ IP(>}B4QMlum~/t?Frܬ%H[|5_4$ ($i@!I IPHҀB4d -?$ (~!H4$ (;6ᘚm¬f0&P!I Q#k$'ރ>7kd f,ᖾ|ϯY!I IPHҀB4$ ($i@!I QrBYd {p~'{a>_!I IP֚m¬f[j m7$ (sFpKݏпsC_Y原4$ ($i@!I IPHҀB4п"K؃v![4Э}ڣJ$ ($i@f0&SM؟f4ۄfM!I_~d-Y#Kxܬ%fa'+B4$ ($i@!I IPHҀB؃,AYa< {z/wlUHҀGa#hZ^R!I IPSMh mEM5ۄfpl)$i@c}nɉ[sF>7kd |nVyouxǯr IPHҀB4$ ($i@!I IPXpd tPjO\厭 IPS^؇p W*$i@!I(qV"IENDB`image/pngchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+object\ text/htmlchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+objectPNG  IHDRi5L()sRGBgAMA a cHRMz&u0`:pQ<FIDATxmo;u =A=u 31|4޶eZ<cĦ#>V1Fl1sr+7x|yOySϴx3-iLgZ<Vfi _ޙi̞'2y"iLg1bSí;WH+g깸Bh7ϴx3-iLgZ<,-} =1OeZ<♽bcĦ#6)ƈM1FaZí;WH+g깸B8V\r'<)LgZ<ϴx3-iLgH+i7*=1ODcĦ#6)ƈ03\! -[qMW<ʴx3-iLgZ<ϴx怴2Kv_יyb'cĦ#>V1F1-9Pu iL=Wh׏o\N*ϴx3-iLgZ<,-";:=1Od_iLg1bS#˜sr+7x|y'iLgZ<ϴx3-iiei̞'2/´x3{)ƈM1F)ƈ?LgTݹBZ9SZĩ⒛7>7ϴx3-iLgZ<,-bM|2-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.

mimetext/htmlrootassigneelast_run_timestampAzpersist_js_state·has_pluto_hook_features§cell_id$79910840-ec59-4433-bfb3-ae2d8da40d22depends_on_disabled_cells§runtime;:published_object_keysdepends_on_skipped_cells§errored$874b6593-7310-4788-beb0-2f18c0ca09a7queued¤logsrunning¦outputbodyf

Three columns in just one JVP

mimetext/htmlrootassigneelast_run_timestampAz/persist_js_state÷has_pluto_hook_features§cell_id$874b6593-7310-4788-beb0-2f18c0ca09a7depends_on_disabled_cells§runtime1published_object_keysdepends_on_skipped_cells§errored$9e24f674-42af-4fa8-bf3e-42e14d855a58queued¤logsrunning¦outputbodychildren

  • 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/htmlchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+objectڞtext/htmlclassnamestyle#display: flex; flex-direction: row;mime'application/vnd.pluto.divelement+objectrootassigneelast_run_timestampAzpersist_js_state·has_pluto_hook_features§cell_id$9e24f674-42af-4fa8-bf3e-42e14d855a58depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$3e6fc4af-19f4-4ff9-b9cf-759e831ff2a4queued¤logsrunning¦outputbodychildrenPNG  IHDRii9 :sRGBgAMA a cHRMz&u0`:pQ<IDATxiXD;0,w2ԁJA {O;SL34/Qogޘy<=tL3T簇ⓙ{HWỹ=L3TyװM2T text/htmlchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+objectOPNG  IHDRl%sRGBgAMA a cHRMz&u0`:pQ<IDATxiPD}`܁P)+އECf-(RQHE"E-5pcRQHEzqOř9$"E*T(RQHE"E*T(RQHE"E*4q2(RQȾ!E*T(RQdZ{k 7&E*T9hgZiC(RQHE"E*T(RQHE"E*T(RQA3w0/"E*aRQHE"E-5ZRQHEzqOř9|{qpT(RQHE"E*T(RQHE"E*T(RQ䠙;p 7HE"E 0pRQHE"E-5ZRQHEzqhߋS=#HE"E*T(RQHE"E*T(RQHE"lo"E* HE"E*TٷZÍIE"EZřf6>gD*T(RQHE"E*T(RQHE"E*T(rsˤHE"{T(RQHE}k -5T(RQ䠵^ifkqy^1!E*T(RQHE"E*T(RQHE"E*T9hf9c RQHE}= 0܀T(RQHE>84IENDB`image/pngclassnamestyle#display: flex; flex-direction: row;mime'application/vnd.pluto.divelement+objectrootassigneelast_run_timestampAzFpersist_js_state·has_pluto_hook_features§cell_id$3e6fc4af-19f4-4ff9-b9cf-759e831ff2a4depends_on_disabled_cells§runtime#^}published_object_keysdepends_on_skipped_cells§errored$2bd9ea13-362e-47ac-b26d-8e36d33e04eaqueued¤logsrunning¦outputbodyH

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_timestampAzLUpersist_js_state÷has_pluto_hook_features§cell_id$2bd9ea13-362e-47ac-b26d-8e36d33e04eadepends_on_disabled_cells§runtime

2 colors with substitutions

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}$$

mimetext/htmlrootassigneelast_run_timestampAzpersist_js_state÷has_pluto_hook_features§cell_id$b33bf212-5f88-47ab-ba10-a2815d17f235depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$d5b7f51b-e451-40a7-aa41-a8006decba33queued¤logsrunning¦outputbody

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.

mimetext/htmlrootassigneelast_run_timestampAzpersist_js_state÷has_pluto_hook_features§cell_id$d5b7f51b-e451-40a7-aa41-a8006decba33depends_on_disabled_cells§runtimefpublished_object_keysdepends_on_skipped_cells§errored$0a91e27f-3cea-415e-aed4-123482da375aqueued¤logsrunning¦outputbody٪

Simple operator overloading implementation

mimetext/htmlrootassigneelast_run_timestampAzpersist_js_state÷has_pluto_hook_features§cell_id$0a91e27f-3cea-415e-aed4-123482da375adepends_on_disabled_cells§runtimexpublished_object_keysdepends_on_skipped_cells§errored$2e3cdd4b-9d04-477c-8c6a-fec6ec846919queued¤logsrunning¦outputbodyprefix&Main.var"workspace#5".MyGradientTracerelementsprefixMyGradientTracerelementsindexsetprefixSet{Int64}elements1text/plaintypeSetprefix_shortSetobjectidc60e8bca9af64a4c!application/vnd.pluto.tree+objecttypestructprefix_shortMyGradientTracerobjectid5cc214671ea5deb9!application/vnd.pluto.tree+objectprefixMyGradientTracerelementsindexsetprefixSet{Int64}elements2text/plaintypeSetprefix_shortSetobjectid7177a634000a037e!application/vnd.pluto.tree+objecttypestructprefix_shortMyGradientTracerobjectid82ac00280c8469bd!application/vnd.pluto.tree+objectprefixMyGradientTracerelementsindexsetprefixSet{Int64}elements3text/plaintypeSetprefix_shortSetobjectidd828032fd65073ad!application/vnd.pluto.tree+objecttypestructprefix_shortMyGradientTracerobjectid541ff05188575793!application/vnd.pluto.tree+objectprefixMyGradientTracerelementsindexsetprefixSet{Int64}elements4text/plaintypeSetprefix_shortSetobjectid79bf56c299f3bde7!application/vnd.pluto.tree+objecttypestructprefix_shortMyGradientTracerobjectid416c29aaba64a816!application/vnd.pluto.tree+objecttypeArrayprefix_shortobjectidb56040426e13c2b1mime!application/vnd.pluto.tree+objectrootassigneextracerlast_run_timestampAzKӰpersist_js_state·has_pluto_hook_features§cell_id$2e3cdd4b-9d04-477c-8c6a-fec6ec846919depends_on_disabled_cells§runtimeqpublished_object_keysdepends_on_skipped_cells§errored$4da92dbb-fcbd-4991-a2f1-f866778a27efqueued¤logsrunning¦outputbody6

Utils

mimetext/htmlrootassigneelast_run_timestampAz˰persist_js_state÷has_pluto_hook_features§cell_id$4da92dbb-fcbd-4991-a2f1-f866778a27efdepends_on_disabled_cells§runtimeYpublished_object_keysdepends_on_skipped_cells§errored$33b368e7-d71e-40ff-8170-a18d11db98fcqueued¤logsrunning¦outputbodychildrenPNG  IHDR0sRGBgAMA a cHRMz&u0`:pQ<IDATxmP~P yub@UA*B A*[kxmqŹ R!H Nk}q;Xi#6| TR!H TR!H TR!H TR!H TR!4s f`/ R!H {5 0G A*B Źmq TR!GXőf>Pa TR!H TR!H TR!H TR!H TR!4s f6 TR!7\àgB A*[kŹ R!H Nk}q;l=Gm$A*B A*B A*B A*B A*Bim˂TR!Hޠg~B A*oq^R!H ‡Yőf>Pa TR!H TR!H TR!H TR!H TR!|= !H T7pA*B A*,LZIENDB`image/pngchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+object* text/htmlchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+objectkPNG  IHDRlDsRGBgAMA a cHRMz&u0`:pQ<IDATxm@DbC(,4{ۓAO]%E*T(RQ{{ -5lL*T(rZ\i'sq9$RQHE"E*T(RQHE"E*T(RQHEf`/"E*7aHE"E*^k{ /HE"ENZ++1$"E*T(RQHE"E*T(RQHE"E*4`s T(RQaC'E*T(RQd{ -5 E*T +1|gq (RQHE"E*T(RQHE"E*T(RQH9-| A*T(aHE"E*?'M\"IENDB`image/pngclassnamestyle#display: flex; flex-direction: row;mime'application/vnd.pluto.divelement+objectrootassigneelast_run_timestampAzo"persist_js_state·has_pluto_hook_features§cell_id$33b368e7-d71e-40ff-8170-a18d11db98fcdepends_on_disabled_cells§runtime& published_object_keysdepends_on_skipped_cells§errored$647c372e-c094-4dfc-8a48-7b7f93fb94ddqueued¤logsrunning¦outputbodychildrenPNG  IHDR0sRGBgAMA a cHRMz&u0`:pQ< IDATxiPpZU.Cؗ$6Pd3A*B A*[\kxmqŵ R!H Ak=8Nc=gmhL $H TR!H TR!H TR!H TR!H Tl6gA*Bxo} R!H TR!Zý-5B A*zpz.4zp#TR!H TR!H TR!H TR!H TR!Hp6_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 Tf=gmdk=8A*B A*B A*B A*B A*B0 1TR!Hp~n H TR!H/f/ q#QIENDB`image/pngchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+object* text/htmlchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+object/PNG  IHDRJsRGBgAMA a cHRMz&u0`:pQ<IDATxщ@~Щ* .ؽ$c"RTD*"{w .HE"R I3'X'1$"RTD*"HE"RTD*"HE"RfNv0 RTD {6 HE"RxpmTD*"Z4sxCB*"HE"RTD*"HE"RTD*"Hhds HEްaRTD*"{w .HE"R I3'X'1$"RTD*"HE"RTD*"HE"RfNv0 RTD {6 HE"RxpmTD*"Z4sxCB*"HE"RTD*"HE"RTD*"Hhds HEްaRTD*"&{IENDB`image/pngclassnamestyle#display: flex; flex-direction: row;mime'application/vnd.pluto.divelement+objectrootassigneelast_run_timestampAz|^persist_js_state·has_pluto_hook_features§cell_id$647c372e-c094-4dfc-8a48-7b7f93fb94dddepends_on_disabled_cells§runtime-Lpublished_object_keysdepends_on_skipped_cells§errored$7fec005c-11b9-4a75-a93c-195d456db190queued¤logsrunning¦outputbodyH

Scalar example

mimetext/htmlrootassigneelast_run_timestampAz persist_js_state÷has_pluto_hook_features§cell_id$7fec005c-11b9-4a75-a93c-195d456db190depends_on_disabled_cells§runtimej_published_object_keysdepends_on_skipped_cells§errored$6bd04f2f-ed5f-4ecf-91dd-8868ec5b83e1queued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAz%-persist_js_state·has_pluto_hook_features§cell_id$6bd04f2f-ed5f-4ecf-91dd-8868ec5b83e1depends_on_disabled_cells§runtime΅xpublished_object_keysdepends_on_skipped_cells§errored$2578b84a-365a-47b6-b58f-1696517c5d02queued¤logsrunning¦outputbodyY

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

mimetext/htmlrootassigneelast_run_timestampAz;persist_js_state÷has_pluto_hook_features§cell_id$2578b84a-365a-47b6-b58f-1696517c5d02depends_on_disabled_cells§runtime gpublished_object_keysdepends_on_skipped_cells§errored$fab75cf6-21cc-4001-84b4-9e66f55d5a6aqueued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAzŰpersist_js_state·has_pluto_hook_features§cell_id$fab75cf6-21cc-4001-84b4-9e66f55d5a6adepends_on_disabled_cells§runtimeepublished_object_keysdepends_on_skipped_cells§errored$29d9f355-26aa-4714-9f9e-3d020016662equeued¤logsrunning¦outputbodyF

Small Example

mimetext/htmlrootassigneelast_run_timestampAzDpersist_js_state÷has_pluto_hook_features§cell_id$29d9f355-26aa-4714-9f9e-3d020016662edepends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$e3dec4ca-69c0-4955-9303-5f8a239546f2queued¤logsrunning¦outputbody٭

Let $h_c$ be the sum of the columns of $B_c$ hence the result of the corresponding HVP.

mimetext/htmlrootassigneelast_run_timestampAzmjpersist_js_state÷has_pluto_hook_features§cell_id$e3dec4ca-69c0-4955-9303-5f8a239546f2depends_on_disabled_cells§runtimeU(published_object_keysdepends_on_skipped_cells§errored$285d3797-5086-4adc-839c-2204128585e1queued¤logsrunning¦outputbody

  • For any pink node $u > 1$, the offdiagonal entry $a_{u,1}$ can be obtained from the yellow HVP.

mimetext/htmlrootassigneelast_run_timestampAz,,persist_js_state÷has_pluto_hook_features§cell_id$285d3797-5086-4adc-839c-2204128585e1depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$0445aae6-2f7e-42b8-b30b-f31298cdeed0queued¤logsrunning¦outputbody

n = 6

mimetext/htmlrootassigneelast_run_timestampAz4persist_js_state·has_pluto_hook_features§cell_id$0445aae6-2f7e-42b8-b30b-f31298cdeed0depends_on_disabled_cells§runtime8published_object_keysdepends_on_skipped_cells§errored$5a6aec48-54fb-4d88-a8a1-b06a2bb99108queued¤logsrunning¦outputbodyٟ4×6 SparseMatrixCSC{Int64, Int64} with 9 stored entries: ⋅ ⋅ 1 1 ⋅ 1 1 ⋅ ⋅ ⋅ 1 ⋅ ⋅ 1 ⋅ ⋅ 1 ⋅ ⋅ 1 1 ⋅ ⋅ ⋅mimetext/plainrootassigneeSlast_run_timestampAzgѰpersist_js_state·has_pluto_hook_features§cell_id$5a6aec48-54fb-4d88-a8a1-b06a2bb99108depends_on_disabled_cells§runtime͌published_object_keysdepends_on_skipped_cells§errored$c2e4982a-3798-4c45-8831-5a76b3b29f6equeued¤logsrunning¦outputbody

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.

mimetext/htmlrootassigneelast_run_timestampAz>persist_js_state÷has_pluto_hook_features§cell_id$c2e4982a-3798-4c45-8831-5a76b3b29f6edepends_on_disabled_cells§runtime/published_object_keysdepends_on_skipped_cells§errored$75597493-3e69-437f-9408-b43a89b35559queued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAzSpersist_js_state·has_pluto_hook_features§cell_id$75597493-3e69-437f-9408-b43a89b35559depends_on_disabled_cells§runtime ypublished_object_keysdepends_on_skipped_cells§errored$1efb0f40-fb9e-4e5b-be59-84910afbf376queued¤logsrunning¦outputbody

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)$$

mimetext/htmlrootassigneelast_run_timestampAzpersist_js_state÷has_pluto_hook_features§cell_id$1efb0f40-fb9e-4e5b-be59-84910afbf376depends_on_disabled_cells§runtimeOĵpublished_object_keysdepends_on_skipped_cells§errored$1167ae71-b63d-4ccc-a120-31c8483eca85queued¤logsrunning¦outputbodyprefixMyGradientTracerelementsindexsetprefixSet{Int64}elements2text/plain3text/plain1text/plaintypeSetprefix_shortSetobjectid3703d3a23e439282!application/vnd.pluto.tree+objecttypestructprefix_shortMyGradientTracerobjectid83147ac30a315acmime!application/vnd.pluto.tree+objectrootassigneeytracerlast_run_timestampAzipersist_js_state·has_pluto_hook_features§cell_id$1167ae71-b63d-4ccc-a120-31c8483eca85depends_on_disabled_cells§runtimezCpublished_object_keysdepends_on_skipped_cells§errored$19dd6563-1a4e-479f-881d-9bcbc720ea36queued¤logsrunning¦outputbody

What color is your Hessian ?

How many HVP do we need to find the values of this sparse symmetric matrix ?

mimetext/htmlrootassigneelast_run_timestampAzʰpersist_js_state÷has_pluto_hook_features§cell_id$19dd6563-1a4e-479f-881d-9bcbc720ea36depends_on_disabled_cells§runtimeNpublished_object_keysdepends_on_skipped_cells§errored$e882ebee-36ad-43d9-8ab7-20f7e8b2d9fequeued¤logsrunning¦outputbodyف

Example

Consider the following sparsity pattern of the Jacobian matrix:

mimetext/htmlrootassigneelast_run_timestampAzֶpersist_js_state÷has_pluto_hook_features§cell_id$e882ebee-36ad-43d9-8ab7-20f7e8b2d9fedepends_on_disabled_cells§runtimeʶpublished_object_keysdepends_on_skipped_cells§errored$cabeb42c-f40b-4549-b9a2-3bda7a988672queued¤logsrunning¦outputbodyimimetext/htmlrootassigneelast_run_timestampAzp.persist_js_state·has_pluto_hook_features§cell_id$cabeb42c-f40b-4549-b9a2-3bda7a988672depends_on_disabled_cells§runtime5published_object_keysdepends_on_skipped_cells§errored$a7e8569e-2fed-4069-aa84-ced67849ab15queued¤logsrunning¦outputbodyl

The same applies to reverse mode

mimetext/htmlrootassigneelast_run_timestampAzz:persist_js_state÷has_pluto_hook_features§cell_id$a7e8569e-2fed-4069-aa84-ced67849ab15depends_on_disabled_cells§runtimeεpublished_object_keysdepends_on_skipped_cells§errored$e721600c-1887-4e99-b474-a427b665e591queued¤logsrunning¦outputbody3
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}$.

mimetext/htmlrootassigneelast_run_timestampAzpersist_js_state·has_pluto_hook_features§cell_id$e721600c-1887-4e99-b474-a427b665e591depends_on_disabled_cells§runtime&published_object_keysdepends_on_skipped_cells§errored$e9135060-75d4-4f5a-9315-2e5fbb493cdfqueued¤logsrunning¦outputbody.colored_plots (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampAz1Ipersist_js_state·has_pluto_hook_features§cell_id$e9135060-75d4-4f5a-9315-2e5fbb493cdfdepends_on_disabled_cells§runtimeApublished_object_keysdepends_on_skipped_cells§errored$d46dcdb3-ac4c-4ba9-ac48-6d6a693630d3queued¤logsrunning¦outputbody"f (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampAz˼persist_js_state·has_pluto_hook_features§cell_id$d46dcdb3-ac4c-4ba9-ac48-6d6a693630d3depends_on_disabled_cells§runtimeYpublished_object_keysdepends_on_skipped_cells§errored$a546edb2-6a72-4c5f-95f7-cc7709bbb505queued¤logsrunning¦outputbodyprefix&Main.var"workspace#5".MyGradientTracerelementsprefixMyGradientTracerelementsindexsetprefixSet{Int64}elements2text/plain1text/plaintypeSetprefix_shortSetobjectid6be79d97dae8ab39!application/vnd.pluto.tree+objecttypestructprefix_shortMyGradientTracerobjectidb86c8db25f0c668!application/vnd.pluto.tree+objectprefixMyGradientTracerelementsindexsetprefixSet{Int64}elements4text/plaintypeSetprefix_shortSetobjectid4727ee8e49053364!application/vnd.pluto.tree+objecttypestructprefix_shortMyGradientTracerobjectid50708f27b2c473c3!application/vnd.pluto.tree+objecttypeArrayprefix_shortobjectid4c4302f8cc188b4mime!application/vnd.pluto.tree+objectrootassigneelast_run_timestampAz$persist_js_state·has_pluto_hook_features§cell_id$a546edb2-6a72-4c5f-95f7-cc7709bbb505depends_on_disabled_cells§runtimeA4published_object_keysdepends_on_skipped_cells§errored$f8e9d672-e6ad-4910-8307-2b56616b11bcqueued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAzүpersist_js_state·has_pluto_hook_features§cell_id$f8e9d672-e6ad-4910-8307-2b56616b11bcdepends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$22c1030b-bef5-4af5-9d5f-6afb4a7ae699queued¤logsrunning¦outputbodyÝmimetext/htmlrootassigneelast_run_timestampAz&persist_js_state·has_pluto_hook_features§cell_id$22c1030b-bef5-4af5-9d5f-6afb4a7ae699depends_on_disabled_cells§runtime?8published_object_keysdepends_on_skipped_cells§errored$18594f1f-6036-4a95-8682-cf415c998311queued¤logsrunning¦outputbodyh

Sparsity detection of Jacobian

mimetext/htmlrootassigneelast_run_timestampAzȰpersist_js_state÷has_pluto_hook_features§cell_id$18594f1f-6036-4a95-8682-cf415c998311depends_on_disabled_cells§runtimekpublished_object_keysdepends_on_skipped_cells§errored$dc23180e-2b0f-41ae-aebf-0159a8f8677aqueued¤logsrunning¦outputbodychildrenG

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/htmlchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+object rtext/htmlclassnamestyle#display: flex; flex-direction: row;mime'application/vnd.pluto.divelement+objectrootassigneelast_run_timestampAzpersist_js_state·has_pluto_hook_features§cell_id$dc23180e-2b0f-41ae-aebf-0159a8f8677adepends_on_disabled_cells§runtime;RXpublished_object_keysdepends_on_skipped_cells§errored$2fe7f4eb-ca33-4338-ba8e-29b769b0dccequeued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAzypersist_js_state·has_pluto_hook_features§cell_id$2fe7f4eb-ca33-4338-ba8e-29b769b0dccedepends_on_disabled_cells§runtimekVpublished_object_keysdepends_on_skipped_cells§errored$97c94c5a-fab5-4226-b803-10c85a298f2aqueued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAzpersist_js_state·has_pluto_hook_features§cell_id$97c94c5a-fab5-4226-b803-10c85a298f2adepends_on_disabled_cells§runtime>published_object_keysdepends_on_skipped_cells§errored$1617c79d-3abe-4ffc-9ee1-3312f2b28eb5queued¤logsrunning¦outputbody

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.

See Section 2.1, 2.2, 3.2 of What color is your Jacobian ?

mimetext/htmlrootassigneelast_run_timestampAzkpersist_js_state÷has_pluto_hook_features§cell_id$1617c79d-3abe-4ffc-9ee1-3312f2b28eb5depends_on_disabled_cells§runtimeopublished_object_keysdepends_on_skipped_cells§errored$8e2045f3-ee09-4439-b504-d2ca9f58a3ddqueued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAz?persist_js_state·has_pluto_hook_features§cell_id$8e2045f3-ee09-4439-b504-d2ca9f58a3dddepends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$f2418632-3261-4acb-8cc6-df333b5480a5queued¤logsrunning¦outputbodyT

Illustrative example

mimetext/htmlrootassigneelast_run_timestampAz)ܰpersist_js_state÷has_pluto_hook_features§cell_id$f2418632-3261-4acb-8cc6-df333b5480a5depends_on_disabled_cells§runtimeܵpublished_object_keysdepends_on_skipped_cells§errored$d0ba0c62-c788-4871-959c-fe7044519849queued¤logsrunning¦outputbody~

Less colors but nontrivial substitution

$$\begin{bmatrix} a_{1} & a_{2} & &\\ a_2 & a_3 & a_4 &\\ & a_4 & a_5 & a_6\\ & & a_6 & a_7 \end{bmatrix}$$

With star coloring, 3 colors:

mimetext/htmlrootassigneelast_run_timestampAz:persist_js_state÷has_pluto_hook_features§cell_id$d0ba0c62-c788-4871-959c-fe7044519849depends_on_disabled_cells§runtimek_published_object_keysdepends_on_skipped_cells§errored$592510fd-a0e4-42e5-ae5b-cac301e74f0aqueued¤logsrunning¦outputbody
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.

mimetext/htmlrootassigneelast_run_timestampAzpersist_js_state·has_pluto_hook_features§cell_id$592510fd-a0e4-42e5-ae5b-cac301e74f0adepends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$5892dfbb-b375-407b-a0a7-da66adb71b67queued¤logsrunning¦outputbody

Theorem 3.5 A coloring of the columns is distance-2 in the bipartite graph iff columns of the same color are structurally orthogonal.

Lemma 3.7 The column intersection graph is the square of the biparted graph restricted to its column vertices.

Lemma 2.1 A coloring is distance-$k$ in $G$ iff it is distance-1 in $G^k$.

mimetext/htmlrootassigneelast_run_timestampAz persist_js_state÷has_pluto_hook_features§cell_id$5892dfbb-b375-407b-a0a7-da66adb71b67depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$fa2a8104-2a3f-438c-bc63-4236a9f5ebebqueued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAzfpersist_js_state·has_pluto_hook_features§cell_id$fa2a8104-2a3f-438c-bc63-4236a9f5ebebdepends_on_disabled_cells§runtime/published_object_keysdepends_on_skipped_cells§errored$aeb8b749-006a-400f-9b7d-05333fd7214fqueued¤logsrunning¦outputbodyh

Whole Jacobian in just two JVP

mimetext/htmlrootassigneelast_run_timestampAzXdpersist_js_state÷has_pluto_hook_features§cell_id$aeb8b749-006a-400f-9b7d-05333fd7214fdepends_on_disabled_cells§runtimeb&published_object_keysdepends_on_skipped_cells§errored$32440932-322a-46ce-911d-5fa6a1136bcaqueued¤logsrunning¦outputbodyv4×4 SparseMatrixCSC{Int64, Int64} with 10 stored entries: 1 2 3 ⋅ 2 4 ⋅ 5 3 ⋅ 6 ⋅ ⋅ 5 ⋅ 7mimetext/plainrootassigneeijkllast_run_timestampAzkCpersist_js_state·has_pluto_hook_features§cell_id$32440932-322a-46ce-911d-5fa6a1136bcadepends_on_disabled_cells§runtime_published_object_keysdepends_on_skipped_cells§errored$e6697119-2801-48e2-b978-facc00af636dqueued¤logsrunning¦outputbody5

Need 3 colors for a path of 4 vertices

$$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}$$

mimetext/htmlrootassigneelast_run_timestampAz-persist_js_state÷has_pluto_hook_features§cell_id$e6697119-2801-48e2-b978-facc00af636ddepends_on_disabled_cells§runtime?published_object_keysdepends_on_skipped_cells§errored$352c92ec-14da-4beb-85c4-f66d77fa42d6queued¤logsrunning¦outputbody R5mimetext/htmlrootassigneelast_run_timestampAzgOpersist_js_state·has_pluto_hook_features§cell_id$352c92ec-14da-4beb-85c4-f66d77fa42d6depends_on_disabled_cells§runtimeu!published_object_keysdepends_on_skipped_cells§errored$21898d8d-f822-4128-ad56-d9a10865fb1dqueued¤logsrunning¦outputbody.three_columns (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampAz]persist_js_state·has_pluto_hook_features§cell_id$21898d8d-f822-4128-ad56-d9a10865fb1ddepends_on_disabled_cells§runtimeV?ܵpublished_object_keysdepends_on_skipped_cells§errored$39e06fde-d734-11f0-a308-89fba7e8abd6queued¤logsrunning¦outputbodyV

Sparse AD

Benoît Legat

      mimetext/htmlrootassigneelast_run_timestampAzΣpersist_js_state·has_pluto_hook_features§cell_id$39e06fde-d734-11f0-a308-89fba7e8abd6depends_on_disabled_cells§runtime0NNpublished_object_keysdepends_on_skipped_cells§errored$726208c6-e856-42a2-b027-555388bc505equeued¤logsrunning¦outputbodychildrentext/htmlchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+objectڦtext/htmlclassnamestyle#display: flex; flex-direction: row;mime'application/vnd.pluto.divelement+objectrootassigneelast_run_timestampAzTpersist_js_state·has_pluto_hook_features§cell_id$726208c6-e856-42a2-b027-555388bc505edepends_on_disabled_cells§runtime%published_object_keysdepends_on_skipped_cells§errored$12ffe7c2-2bf6-4949-ae28-f3d8e03a5da5queued¤logsrunning¦outputbodychildrenS

Color's columns are structurally orthogonal

text/htmlchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+object7

Jacobian from 3 JVP

text/htmlclassnamestyle#display: flex; flex-direction: row;mime'application/vnd.pluto.divelement+objectrootassigneelast_run_timestampAzcpersist_js_state·has_pluto_hook_features§cell_id$12ffe7c2-2bf6-4949-ae28-f3d8e03a5da5depends_on_disabled_cells§runtime;=published_object_keysdepends_on_skipped_cells§errored$9df9c76a-48af-4ca6-83f1-b8798d6d4e34queued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAz҈ΰpersist_js_state·has_pluto_hook_features§cell_id$9df9c76a-48af-4ca6-83f1-b8798d6d4e34depends_on_disabled_cells§runtime%published_object_keysdepends_on_skipped_cells§errored$76162106-fb90-4883-b2d2-b87e1419c072queued¤logsrunning¦outputbodyj

Formulation as coloring problem

mimetext/htmlrootassigneelast_run_timestampAzpersist_js_state÷has_pluto_hook_features§cell_id$76162106-fb90-4883-b2d2-b87e1419c072depends_on_disabled_cells§runtimeIpublished_object_keysdepends_on_skipped_cells§errored$760ef943-e9d9-4cdc-8977-932cf6fcb78aqueued¤logsrunning¦outputbodyP

Coloring of a star

mimetext/htmlrootassigneelast_run_timestampAzpersist_js_state÷has_pluto_hook_features§cell_id$760ef943-e9d9-4cdc-8977-932cf6fcb78adepends_on_disabled_cells§runtime1published_object_keysdepends_on_skipped_cells§errored$a01688ec-8f16-4d39-b39d-6d1acd24d7adqueued¤logsrunning¦outputbodychildrentext/htmlchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+objectڡtext/htmlclassnamestyle#display: flex; flex-direction: row;mime'application/vnd.pluto.divelement+objectrootassigneelast_run_timestampAzTpersist_js_state·has_pluto_hook_features§cell_id$a01688ec-8f16-4d39-b39d-6d1acd24d7addepends_on_disabled_cells§runtime\published_object_keysdepends_on_skipped_cells§errored$a3bf5961-323b-4adc-99a0-9a456a0bfd48queued¤logsrunning¦outputbody"F (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampAz!׿persist_js_state·has_pluto_hook_features§cell_id$a3bf5961-323b-4adc-99a0-9a456a0bfd48depends_on_disabled_cells§runtime ?published_object_keysdepends_on_skipped_cells§errored$d23e7238-5edb-42d3-96d9-0dffa9e7f326queued¤logsrunning¦outputbodychildrenْ

scale =

text/htmlٍ

pad =

text/htmlْ

border =

text/htmlclassnamestyle#display: flex; flex-direction: row;mime'application/vnd.pluto.divelement+objectrootassigneelast_run_timestampAz)%persist_js_state·has_pluto_hook_features§cell_id$d23e7238-5edb-42d3-96d9-0dffa9e7f326depends_on_disabled_cells§runtimeٵpublished_object_keysdepends_on_skipped_cells§errored$a7b85908-404b-475b-9875-c1190de5ff71queued¤logsrunning¦outputbody

  • Each off-diagonal entry $a_{uv}$ corresponds to an edge in the graph.

  • The edge links nodes $u, v$ of 2 different colors $\phi(u)$ and $\phi(v)$

  • If $u$ is not adjacent to any other nodes of color $\phi(v)$ then $a_{uv}$ is the only term at the row $u$ of the HVP of color $\phi(v)$

mimetext/htmlrootassigneelast_run_timestampAz&persist_js_state÷has_pluto_hook_features§cell_id$a7b85908-404b-475b-9875-c1190de5ff71depends_on_disabled_cells§runtime_~published_object_keysdepends_on_skipped_cells§errored$15cf368c-cada-4a72-b59b-a0f9dd0115b4queued¤logsrunning¦outputbody
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}$

mimetext/htmlrootassigneelast_run_timestampAzopersist_js_state·has_pluto_hook_features§cell_id$15cf368c-cada-4a72-b59b-a0f9dd0115b4depends_on_disabled_cells§runtimeDpublished_object_keysdepends_on_skipped_cells§errored$70296870-49af-4564-bdb7-bd2d49f9114bqueued¤logsrunning¦outputbodychildrenPNG  IHDRii9 :sRGBgAMA a cHRMz&u0`:pQ<IDATx XCC\:pw*ArSL3 ׈2\#^kpx?g<8CxgZyghw9%ޙpxgZg♊g*x♊g*x]Z.-qKKܥ%2}>qOd*xfoF ׈:d*90 iygh5SL3T text/htmlchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+objectPNG  IHDRJV_sRGBgAMA a cHRMz&u0`:pQ<lIDATxщ@~Щ* .ؽ$c"RTD*"{w .HE"R I3'X'1$"RTD*"HE"RTD*"HE"RfNv0 RTD {6 HE"RxpmTD*"Z4sxCB*"HE"RTD*"HE"RTD*"Hhds HEްaRTD*"{w .HE"R I3'X'1$"RTD*"HE"RTD*"HE"RfNv0 RTD {6 HE"RxpmTD*"Z4sxCB*"HE"RTD*"HE"RTD*"Hhds HEްaRTD*"{w .HE"R I3'X'1$"RTD*"HE"RTD*"HE"RfNv0 RTD {6 HE"RxpmTD*"Z4sxCB*"HE"RTD*"HE"RTD*"Hhds HEްaRTD*"ϡ9IENDB`image/pngclassnamestyle#display: flex; flex-direction: row;mime'application/vnd.pluto.divelement+objectrootassigneelast_run_timestampAziUpersist_js_state·has_pluto_hook_features§cell_id$70296870-49af-4564-bdb7-bd2d49f9114bdepends_on_disabled_cells§runtime?Apublished_object_keysdepends_on_skipped_cells§errored$45f4edeb-d934-413f-9f45-568465111b6equeued¤logsrunning¦outputbody|

Sparsity detection with multiple outputs

mimetext/htmlrootassigneelast_run_timestampAz0Mpersist_js_state÷has_pluto_hook_features§cell_id$45f4edeb-d934-413f-9f45-568465111b6edepends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166queued¤logsrunning¦outputbody$viz (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampAzٰpersist_js_state·has_pluto_hook_features§cell_id$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166depends_on_disabled_cells§runtime끵published_object_keysdepends_on_skipped_cells§errored$9b427766-5290-4dee-8dd5-5aab20080d0aqueued¤logsrunning¦outputbodychildrenPNG  IHDRsRGBgAMA a cHRMz&u0`:pQ<IDATxm E:e@gtfRNA^ `^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 IPfS8B4$ ($i@!I IPHҀB̽S4^п IPHҀBlm>f0&|SHҀBə[Ҭ%zkV9:/$ ($i@!I IPHҀB4(9s,Av IPwt[؇pB48f?6amni W6BəKF{o*u~Ou^I!I IPHҀB4$ ($i@!IKEpYO IPW8pA IPHҀBEMlm4ۄ)$i@53֬r Y#KؽfSثB4$ ($i@!I IPHҀBP3p v$ (Q} $ (;6ᘚm15ۄ*$i@?~fGЗf,CxkV9#+$i@!I IPHҀB4$ ($i@?J*KwNAPHҀB$ (&SMj mUM8f0ŎY#KҬ%əzkV9[Ҭ%|_?bw$ ($i@!I IPHҀB4Ŏe مSWwO$ (){~av$ (~lw6aVMj m4gHəzkV9[Ҭ%<[)Y!I IPHҀB4$ ($i@!I_H蘒3p v$ (~tTa>$ (~lf5if_*$i@ Ϭy4kd &o*+$i@!I IPHҀB4$ ($i@ ə=:($i@AzQ$ ($i@i lf5ۄY6 IP菺Y#9Y#Kx4kd ֬r GVHҀB4$ ($i@!I IPHҀBUY.~'{a>$ (h6aVM#5ۄY6BOY#KxgH?֬r u^I!I IPHҀB4$ ($i@!I '=HhNa^ج-C}w*$i@!I5ۄY6ᘚm4lm7$ (~53ԗf,#KF{o*u~Ou^I!I IPHҀB4$ ($i@!I_HA,0NA^߹ 4Q؇THҀBlm¬fplw6&\5ۄo IPX_5[Y#9H}inKF[)'xz}/O IPHҀB4$ ($i@!I IPXpd tPpwf$ ()/C_Q;4ү!] IENDB`image/pngchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+object\ text/htmlchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+objecthPNG  IHDRX}/sRGBgAMA a cHRMz&u0`:pQ<IDATxioÞv ΠjA=Xt ༉yBXqoojs2-ʴ(Ӣ^1Fl1bSbL2\!Gqq꣸&+^?I0-ʴ(ӢL2-ʴ(ӢL2-Vfinb'%Ӣ̞'y eZ+ƈM1F@EUwVԣBL2-ʴ(ӢL2-ʴ(ӢL2YZDӢ̞'eZ+ƈM1Fl1bSbbZ9Pu iL=+S%7q_\ɩWyӢL2-ʴ(ӢL2-ʴ(Ӣie1&f2aE=1O<1ɴ(Ӣ^1Fl1cӢ́;WH+gQ\EKn"kƴ(ӢL2-ʴ(ӢL2-ʴ(s@ZEL0Ӣ̞' &eZ+ƈM1Fl1bSbbZ9Pu iL=+S%7q_\ɩWyӢL2-ʴ(ӢL2-ʴ(Ӣie1&f2aE=1O<1ɴ(Ӣ^1Fl1bSOƴ(sʙzWh>KnYeZiQEeZiQEeH+i73-yb!L2-cĦ#6dL2\!Gqq꣸&iQEeZiQEeZiQ怴2Kv:Ӣ̞'´(Ӣ^1Fl1bSbL2\!Gqq꣸&+^?I0-ʴ(ӢL2-ʴ(ӢL2-Vfinb'%Ӣ̞'y eZ+ƈM1Fl1ɘeTݹBZ9S -GqM<+ӢL2-ʴ(ӢL2-ʴ(Ӣie1&uE=1O?iQEbcĦ#iQ@՝+3("N}ij2-ʴ(ӢL2-ʴ(ӢL2-Vfin_gZFrom 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.

mimetext/htmlrootassigneelast_run_timestampAz]persist_js_state·has_pluto_hook_features§cell_id$26191290-2b2d-43fe-b2bf-d690fd0bbe15depends_on_disabled_cells§runtimeJԵpublished_object_keysdepends_on_skipped_cells§errored$e3ae5697-6b0b-4d5f-99a0-d579b6eff655queued¤logsrunning¦outputbody

Acyclic coloring

Definition 6.3 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 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.

mimetext/htmlrootassigneelast_run_timestampAzpersist_js_state÷has_pluto_hook_features§cell_id$e3ae5697-6b0b-4d5f-99a0-d579b6eff655depends_on_disabled_cells§runtime {published_object_keysdepends_on_skipped_cells§errored$b18a3bf6-102e-49f5-af8c-f1c35d2e2a8bqueued¤logsrunning¦outputbody

The sign function is constant over $x > 0$ and $x < 0$ so its output carries no variables

mimetext/htmlrootassigneelast_run_timestampAz声persist_js_state÷has_pluto_hook_features§cell_id$b18a3bf6-102e-49f5-af8c-f1c35d2e2a8bdepends_on_disabled_cells§runtime5Apublished_object_keysdepends_on_skipped_cells§errored$e2eb1894-06ad-47a0-9ee0-c65b24a669b5queued¤logsrunning¦outputbody
mimetext/htmlrootassigneelast_run_timestampAzdpersist_js_state÷has_pluto_hook_features§cell_id$e2eb1894-06ad-47a0-9ee0-c65b24a669b5depends_on_disabled_cells§runtime7published_object_keysdepends_on_skipped_cells§errored$95d7e9cd-b4a1-4205-b7d4-8c10916be8a2queued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAzpersist_js_state·has_pluto_hook_features§cell_id$95d7e9cd-b4a1-4205-b7d4-8c10916be8a2depends_on_disabled_cells§runtime _篵published_object_keysdepends_on_skipped_cells§errored$884f9025-10e9-4657-88ec-55e6c9b6d530queued¤logsrunning¦outputbodychildrenPNG  IHDR0sRGBgAMA a cHRMz&u0`:pQ< IDATx@DNGa) 6,4$t¯*H TR!H g{ -5诂TR!HpZ/4sX_+sп R!H TR!H TR!H TR!H TR!H I3;B A*φ= N A*B Ž[kX A*NZŕfkqy^\i' R!H TR!H TR!H TR!H TR!H I3;簃Y A*>0aA*B A*-5^A*BaJkAR TR!H TR!H TR!H TR!H TR!0v0sTR!Ha B A*t^{{ oB A^\ikqpF A*B A*B A*B A*B A*T9cA*BY B A*R,KIENDB`image/pngchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+object* text/htmlchildren text/htmlclassnamestyleflex-grow: 1;'application/vnd.pluto.divelement+objectlPNG  IHDRlDsRGBgAMA a cHRMz&u0`:pQ<IDATxiPD}`܁P)+އECf-(RQHE"E-5pcRQHEzqOř9$"E*T(RQHE"E*T(RQHE"E*4q2(RQȾ!E*T(RQdZ{k 7&E*T9hgZiC(RQHE"E*T(RQHE"E*T(RQA3w0/"E*aRQHE"E-5ZRQHEzqOř9|{qpT(RQHE"E*T(RQHE"E*T(RQ䠙;p 7HE"E 0pRQHE"E-5ZRQHEzqhߋS=#HE"E*T(RQHE"E*T(RQHE"lo"E* HE"E*T( k4IENDB`image/pngclassnamestyle#display: flex; flex-direction: row;mime'application/vnd.pluto.divelement+objectrootassigneelast_run_timestampAzJSpersist_js_state·has_pluto_hook_features§cell_id$884f9025-10e9-4657-88ec-55e6c9b6d530depends_on_disabled_cells§runtime" ׵published_object_keysdepends_on_skipped_cells§errored$44a6b427-bd4b-4fa1-95d8-a8ea55719192queued¤logsrunning¦outputbody
How can the diagonal entries be determined ?

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$.

mimetext/htmlrootassigneelast_run_timestampAzClpersist_js_state·has_pluto_hook_features§cell_id$44a6b427-bd4b-4fa1-95d8-a8ea55719192depends_on_disabled_cells§runtime&published_object_keysdepends_on_skipped_cells§errored$dfe3dffd-926b-4083-9e66-8536e5df198dqueued¤logsrunning¦outputbody$qa (generic function with 2 methods)mimetext/plainrootassigneelast_run_timestampAzpersist_js_state·has_pluto_hook_features§cell_id$dfe3dffd-926b-4083-9e66-8536e5df198ddepends_on_disabled_cells§runtimeߩpublished_object_keysdepends_on_skipped_cells§errored$04ea8b79-63ba-4eb4-938c-98a21668924aqueued¤logsrunning¦outputbody
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.

mimetext/htmlrootassigneelast_run_timestampAzpersist_js_state·has_pluto_hook_features§cell_id$04ea8b79-63ba-4eb4-938c-98a21668924adepends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$dbef0e7d-b731-4d83-98e3-104b23f26042queued¤logsrunning¦outputbody

n = 16

mimetext/htmlrootassigneelast_run_timestampAzpersist_js_state·has_pluto_hook_features§cell_id$dbef0e7d-b731-4d83-98e3-104b23f26042depends_on_disabled_cells§runtime2published_object_keysdepends_on_skipped_cells§errored±cell_dependenciesU$a5769449-96cd-477a-bceb-ad9439a37430precedence_heuristic cell_id$a5769449-96cd-477a-bceb-ad9439a37430downstream_cells_mapupstream_cells_map@md_strimg$2728dc2c-ca17-4989-9259-451f95a24bd2getindex$a4ecf92d-6c45-4112-8f0c-06a6d227cd84precedence_heuristic cell_id$a4ecf92d-6c45-4112-8f0c-06a6d227cd84downstream_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$91226321-fc72-4bd9-8d78-9c2bff5c760aprecedence_heuristic cell_id$91226321-fc72-4bd9-8d78-9c2bff5c760adownstream_cells_mapupstream_cells_mapS$5a6aec48-54fb-4d88-a8a1-b06a2bb99108viz$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166*cm$6c174bac-faef-424a-9de7-e4c7be8ddb27precedence_heuristic cell_id$6c174bac-faef-424a-9de7-e4c7be8ddb27downstream_cells_mapupstream_cells_map@md_strgetindex$2728dc2c-ca17-4989-9259-451f95a24bd2precedence_heuristic cell_id$2728dc2c-ca17-4989-9259-451f95a24bd2downstream_cells_mapsave_imagePath$2728dc2c-ca17-4989-9259-451f95a24bd2imgpathURL$2728dc2c-ca17-4989-9259-451f95a24bd2img$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-6afb4a7ae699upstream_cells_map!HypertextLiteral.BypassPlutoUI.LocalResourcePlutoUI$75597493-3e69-437f-9408-b43a89b35559joinpathHypertextLiteral.contentstartswithStringendPlutoTeachingTools$75597493-3e69-437f-9408-b43a89b35559@htlHypertextLiteral.attribute_pair&PlutoTeachingTools.RobustLocalResourcePath$2728dc2c-ca17-4989-9259-451f95a24bd2HypertextLiteral.ResultHypertextLiteral$75597493-3e69-437f-9408-b43a89b35559URL$2728dc2c-ca17-4989-9259-451f95a24bd2*@__DIR__insplit$a413c12c-72c1-4f46-b7f2-0b0118c1b232precedence_heuristic cell_id$a413c12c-72c1-4f46-b7f2-0b0118c1b232downstream_cells_mapupstream_cells_mapviz$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166*large$2fe7f4eb-ca33-4338-ba8e-29b769b0dccecm$79910840-ec59-4433-bfb3-ae2d8da40d22precedence_heuristic cell_id$79910840-ec59-4433-bfb3-ae2d8da40d22downstream_cells_mapupstream_cells_map@md_strqa$dfe3dffd-926b-4083-9e66-8536e5df198dgetindex$874b6593-7310-4788-beb0-2f18c0ca09a7precedence_heuristic cell_id$874b6593-7310-4788-beb0-2f18c0ca09a7downstream_cells_mapupstream_cells_map@md_strgetindex$9e24f674-42af-4fa8-bf3e-42e14d855a58precedence_heuristic cell_id$9e24f674-42af-4fa8-bf3e-42e14d855a58downstream_cells_mapupstream_cells_map@md_strtwo_columns$e820e135-2df2-4fa3-a09b-8ce7e5a1f745=>img$2728dc2c-ca17-4989-9259-451f95a24bd2getindex$3e6fc4af-19f4-4ff9-b9cf-759e831ff2a4precedence_heuristic cell_id$3e6fc4af-19f4-4ff9-b9cf-759e831ff2a4downstream_cells_mapupstream_cells_mapSparseMatrixColorings$6bd04f2f-ed5f-4ecf-91dd-8868ec5b83e1viz$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166!SparseMatrixColorings.what_fig_41*cm$2bd9ea13-362e-47ac-b26d-8e36d33e04eaprecedence_heuristic cell_id$2bd9ea13-362e-47ac-b26d-8e36d33e04eadownstream_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$d5b7f51b-e451-40a7-aa41-a8006decba33precedence_heuristic cell_id$d5b7f51b-e451-40a7-aa41-a8006decba33downstream_cells_mapupstream_cells_map@md_strgetindex$0a91e27f-3cea-415e-aed4-123482da375aprecedence_heuristic cell_id$0a91e27f-3cea-415e-aed4-123482da375adownstream_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_mapMyGradientTracer$97c94c5a-fab5-4226-b803-10c85a298f2aSet$4da92dbb-fcbd-4991-a2f1-f866778a27efprecedence_heuristic cell_id$4da92dbb-fcbd-4991-a2f1-f866778a27efdownstream_cells_mapupstream_cells_map@md_strgetindex$33b368e7-d71e-40ff-8170-a18d11db98fcprecedence_heuristic cell_id$33b368e7-d71e-40ff-8170-a18d11db98fcdownstream_cells_mapupstream_cells_mapviz$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166ijkl$32440932-322a-46ce-911d-5fa6a1136bca*cm$647c372e-c094-4dfc-8a48-7b7f93fb94ddprecedence_heuristic cell_id$647c372e-c094-4dfc-8a48-7b7f93fb94dddownstream_cells_mapupstream_cells_mapviz$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166ijkl$32440932-322a-46ce-911d-5fa6a1136bca*cm$7fec005c-11b9-4a75-a93c-195d456db190precedence_heuristic cell_id$7fec005c-11b9-4a75-a93c-195d456db190downstream_cells_mapupstream_cells_map@md_strgetindex$6bd04f2f-ed5f-4ecf-91dd-8868ec5b83e1precedence_heuristiccell_id$6bd04f2f-ed5f-4ecf-91dd-8868ec5b83e1downstream_cells_mapSparseMatrixColorings$3e6fc4af-19f4-4ff9-b9cf-759e831ff2a4$e9135060-75d4-4f5a-9315-2e5fbb493cdfImagesSparseArraysupstream_cells_map$2578b84a-365a-47b6-b58f-1696517c5d02precedence_heuristic cell_id$2578b84a-365a-47b6-b58f-1696517c5d02downstream_cells_mapupstream_cells_map@md_strgetindex$fab75cf6-21cc-4001-84b4-9e66f55d5a6aprecedence_heuristic cell_id$fab75cf6-21cc-4001-84b4-9e66f55d5a6adownstream_cells_mapijkl2$884f9025-10e9-4657-88ec-55e6c9b6d530upstream_cells_mapsparse$29d9f355-26aa-4714-9f9e-3d020016662eprecedence_heuristic cell_id$29d9f355-26aa-4714-9f9e-3d020016662edownstream_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$285d3797-5086-4adc-839c-2204128585e1precedence_heuristic cell_id$285d3797-5086-4adc-839c-2204128585e1downstream_cells_mapupstream_cells_map@md_strgetindex$0445aae6-2f7e-42b8-b30b-f31298cdeed0precedence_heuristic cell_id$0445aae6-2f7e-42b8-b30b-f31298cdeed0downstream_cells_mapstar_n$95d7e9cd-b4a1-4205-b7d4-8c10916be8a2upstream_cells_map@md_strCore:Base.get@bindSliderBasePlutoRunnerPlutoRunner.create_bondCore.applicablegetindex$5a6aec48-54fb-4d88-a8a1-b06a2bb99108precedence_heuristic cell_id$5a6aec48-54fb-4d88-a8a1-b06a2bb99108downstream_cells_mapS$91226321-fc72-4bd9-8d78-9c2bff5c760aupstream_cells_mapsparse$c2e4982a-3798-4c45-8831-5a76b3b29f6eprecedence_heuristic cell_id$c2e4982a-3798-4c45-8831-5a76b3b29f6edownstream_cells_mapupstream_cells_map@md_strgetindex$75597493-3e69-437f-9408-b43a89b35559precedence_heuristiccell_id$75597493-3e69-437f-9408-b43a89b35559downstream_cells_mapPlutoUI$39e06fde-d734-11f0-a308-89fba7e8abd6$2728dc2c-ca17-4989-9259-451f95a24bd2HypertextLiteral$39e06fde-d734-11f0-a308-89fba7e8abd6$2728dc2c-ca17-4989-9259-451f95a24bd2$dfe3dffd-926b-4083-9e66-8536e5df198dExperimentalLayoutPlutoTeachingTools$39e06fde-d734-11f0-a308-89fba7e8abd6$2728dc2c-ca17-4989-9259-451f95a24bd2upstream_cells_map$1efb0f40-fb9e-4e5b-be59-84910afbf376precedence_heuristic cell_id$1efb0f40-fb9e-4e5b-be59-84910afbf376downstream_cells_mapupstream_cells_map@md_strgetindex$1167ae71-b63d-4ccc-a120-31c8483eca85precedence_heuristic cell_id$1167ae71-b63d-4ccc-a120-31c8483eca85downstream_cells_mapytracerupstream_cells_mapxtracer$2e3cdd4b-9d04-477c-8c6a-fec6ec846919f$d46dcdb3-ac4c-4ba9-ac48-6d6a693630d3$19dd6563-1a4e-479f-881d-9bcbc720ea36precedence_heuristic cell_id$19dd6563-1a4e-479f-881d-9bcbc720ea36downstream_cells_mapupstream_cells_map@md_strgetindex$e882ebee-36ad-43d9-8ab7-20f7e8b2d9feprecedence_heuristic cell_id$e882ebee-36ad-43d9-8ab7-20f7e8b2d9fedownstream_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-451f95a24bd2$a7e8569e-2fed-4069-aa84-ced67849ab15precedence_heuristic cell_id$a7e8569e-2fed-4069-aa84-ced67849ab15downstream_cells_mapupstream_cells_map@md_strgetindex$e721600c-1887-4e99-b474-a427b665e591precedence_heuristic cell_id$e721600c-1887-4e99-b474-a427b665e591downstream_cells_mapupstream_cells_map@md_strqa$dfe3dffd-926b-4083-9e66-8536e5df198dgetindex$e9135060-75d4-4f5a-9315-2e5fbb493cdfprecedence_heuristic cell_id$e9135060-75d4-4f5a-9315-2e5fbb493cdfdownstream_cells_mapcolored_plots$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166upstream_cells_mapColoringProblemRGBconvertadjoint$SparseMatrixColorings.AdjacencyGraphscale$d23e7238-5edb-42d3-96d9-0dffa9e7f326!SparseMatrixColorings.show_colorsGreedyColoringAlgorithmGraphs$4f8de444-dcb4-411a-b087-6948699614e0==conjdistinguishable_colorscoloringdiagncolorsborder$d23e7238-5edb-42d3-96d9-0dffa9e7f326gplotRGBASparseMatrixColorings$6bd04f2f-ed5f-4ecf-91dd-8868ec5b83e1pad$d23e7238-5edb-42d3-96d9-0dffa9e7f326Diagonal-*Graphs.SimpleDiGraph$d46dcdb3-ac4c-4ba9-ac48-6d6a693630d3precedence_heuristic cell_id$d46dcdb3-ac4c-4ba9-ac48-6d6a693630d3downstream_cells_mapf$1167ae71-b63d-4ccc-a120-31c8483eca85upstream_cells_mapsign+*$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$f8e9d672-e6ad-4910-8307-2b56616b11bcprecedence_heuristic cell_id$f8e9d672-e6ad-4910-8307-2b56616b11bcdownstream_cells_mapBase.signupstream_cells_mapBaseMyGradientTracer$97c94c5a-fab5-4226-b803-10c85a298f2aSet$22c1030b-bef5-4af5-9d5f-6afb4a7ae699precedence_heuristic cell_id$22c1030b-bef5-4af5-9d5f-6afb4a7ae699downstream_cells_mapupstream_cells_mapimg$2728dc2c-ca17-4989-9259-451f95a24bd2$18594f1f-6036-4a95-8682-cf415c998311precedence_heuristic cell_id$18594f1f-6036-4a95-8682-cf415c998311downstream_cells_mapupstream_cells_map@md_strgetindex$dc23180e-2b0f-41ae-aebf-0159a8f8677aprecedence_heuristic cell_id$dc23180e-2b0f-41ae-aebf-0159a8f8677adownstream_cells_mapupstream_cells_map@md_strtwo_columns$e820e135-2df2-4fa3-a09b-8ce7e5a1f745=>img$2728dc2c-ca17-4989-9259-451f95a24bd2getindex$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_mapn$dbef0e7d-b731-4d83-98e3-104b23f26042ISymmetricsprand+BoolsparseStableRNG$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$1617c79d-3abe-4ffc-9ee1-3312f2b28eb5precedence_heuristic cell_id$1617c79d-3abe-4ffc-9ee1-3312f2b28eb5downstream_cells_mapupstream_cells_map@md_strgetindex$8e2045f3-ee09-4439-b504-d2ca9f58a3ddprecedence_heuristic cell_id$8e2045f3-ee09-4439-b504-d2ca9f58a3dddownstream_cells_mapBase.+upstream_cells_mapBaseunionMyGradientTracer$97c94c5a-fab5-4226-b803-10c85a298f2a$f2418632-3261-4acb-8cc6-df333b5480a5precedence_heuristic cell_id$f2418632-3261-4acb-8cc6-df333b5480a5downstream_cells_mapupstream_cells_map@md_strgetindex$d0ba0c62-c788-4871-959c-fe7044519849precedence_heuristic cell_id$d0ba0c62-c788-4871-959c-fe7044519849downstream_cells_mapupstream_cells_map@md_strgetindex$592510fd-a0e4-42e5-ae5b-cac301e74f0aprecedence_heuristic cell_id$592510fd-a0e4-42e5-ae5b-cac301e74f0adownstream_cells_mapupstream_cells_map@md_strqa$dfe3dffd-926b-4083-9e66-8536e5df198dgetindex$5892dfbb-b375-407b-a0a7-da66adb71b67precedence_heuristic cell_id$5892dfbb-b375-407b-a0a7-da66adb71b67downstream_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$aeb8b749-006a-400f-9b7d-05333fd7214fprecedence_heuristic cell_id$aeb8b749-006a-400f-9b7d-05333fd7214fdownstream_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$e6697119-2801-48e2-b978-facc00af636dprecedence_heuristic cell_id$e6697119-2801-48e2-b978-facc00af636ddownstream_cells_mapupstream_cells_map@md_strgetindex$352c92ec-14da-4beb-85c4-f66d77fa42d6precedence_heuristic cell_id$352c92ec-14da-4beb-85c4-f66d77fa42d6downstream_cells_mapupstream_cells_map=>img$2728dc2c-ca17-4989-9259-451f95a24bd2$21898d8d-f822-4128-ad56-d9a10865fb1dprecedence_heuristic cell_id$21898d8d-f822-4128-ad56-d9a10865fb1ddownstream_cells_mapthree_columns$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166upstream_cells_mapDicthboxBaseBase.Docs.HTML@html_strDiv=>$39e06fde-d734-11f0-a308-89fba7e8abd6precedence_heuristic cell_id$39e06fde-d734-11f0-a308-89fba7e8abd6downstream_cells_mapupstream_cells_mapPlutoTeachingTools$75597493-3e69-437f-9408-b43a89b35559HypertextLiteral.BypassHypertextLiteral.ResultHypertextLiteral$75597493-3e69-437f-9408-b43a89b35559PlutoUI$75597493-3e69-437f-9408-b43a89b35559HypertextLiteral.content$PlutoTeachingTools.ChooseDisplayMode@htlPlutoUI.TableOfContents$726208c6-e856-42a2-b027-555388bc505eprecedence_heuristic cell_id$726208c6-e856-42a2-b027-555388bc505edownstream_cells_mapupstream_cells_maptwo_columns$e820e135-2df2-4fa3-a09b-8ce7e5a1f745img$2728dc2c-ca17-4989-9259-451f95a24bd2$12ffe7c2-2bf6-4949-ae28-f3d8e03a5da5precedence_heuristic cell_id$12ffe7c2-2bf6-4949-ae28-f3d8e03a5da5downstream_cells_mapupstream_cells_map@md_strtwo_columns$e820e135-2df2-4fa3-a09b-8ce7e5a1f745getindex$9df9c76a-48af-4ca6-83f1-b8798d6d4e34precedence_heuristic cell_id$9df9c76a-48af-4ca6-83f1-b8798d6d4e34downstream_cells_mapBase./upstream_cells_mapBaseMyGradientTracer$97c94c5a-fab5-4226-b803-10c85a298f2aNumber$76162106-fb90-4883-b2d2-b87e1419c072precedence_heuristic cell_id$76162106-fb90-4883-b2d2-b87e1419c072downstream_cells_mapupstream_cells_map@md_strgetindex$760ef943-e9d9-4cdc-8977-932cf6fcb78aprecedence_heuristic cell_id$760ef943-e9d9-4cdc-8977-932cf6fcb78adownstream_cells_mapupstream_cells_map@md_strgetindex$a01688ec-8f16-4d39-b39d-6d1acd24d7adprecedence_heuristic cell_id$a01688ec-8f16-4d39-b39d-6d1acd24d7addownstream_cells_mapupstream_cells_maptwo_columns$e820e135-2df2-4fa3-a09b-8ce7e5a1f745=>img$2728dc2c-ca17-4989-9259-451f95a24bd2$a3bf5961-323b-4adc-99a0-9a456a0bfd48precedence_heuristic cell_id$a3bf5961-323b-4adc-99a0-9a456a0bfd48downstream_cells_mapF$a546edb2-6a72-4c5f-95f7-cc7709bbb505upstream_cells_mapsign/+*$d23e7238-5edb-42d3-96d9-0dffa9e7f326precedence_heuristic cell_id$d23e7238-5edb-42d3-96d9-0dffa9e7f326downstream_cells_mappad$e9135060-75d4-4f5a-9315-2e5fbb493cdfborder$e9135060-75d4-4f5a-9315-2e5fbb493cdfscale$e9135060-75d4-4f5a-9315-2e5fbb493cdfupstream_cells_map@md_strhbox:CoreBase.get@bindSliderBasePlutoRunnerPlutoRunner.create_bondCore.applicablegetindex$a7b85908-404b-475b-9875-c1190de5ff71precedence_heuristic cell_id$a7b85908-404b-475b-9875-c1190de5ff71downstream_cells_mapupstream_cells_map@md_strgetindex$15cf368c-cada-4a72-b59b-a0f9dd0115b4precedence_heuristic cell_id$15cf368c-cada-4a72-b59b-a0f9dd0115b4downstream_cells_mapupstream_cells_map@md_strqa$dfe3dffd-926b-4083-9e66-8536e5df198dgetindex$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-8c10916be8a2*cm$45f4edeb-d934-413f-9f45-568465111b6eprecedence_heuristic cell_id$45f4edeb-d934-413f-9f45-568465111b6edownstream_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$884f9025-10e9-4657-88ec-55e6c9b6d530$647c372e-c094-4dfc-8a48-7b7f93fb94dd$a413c12c-72c1-4f46-b7f2-0b0118c1b232$9b427766-5290-4dee-8dd5-5aab20080d0aupstream_cells_mapthree_columns$21898d8d-f822-4128-ad56-d9a10865fb1dcolored_plots$e9135060-75d4-4f5a-9315-2e5fbb493cdf$9b427766-5290-4dee-8dd5-5aab20080d0aprecedence_heuristic cell_id$9b427766-5290-4dee-8dd5-5aab20080d0adownstream_cells_mapupstream_cells_mapviz$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166*large$2fe7f4eb-ca33-4338-ba8e-29b769b0dccecm$4f8de444-dcb4-411a-b087-6948699614e0precedence_heuristiccell_id$4f8de444-dcb4-411a-b087-6948699614e0downstream_cells_mapGraphs$e9135060-75d4-4f5a-9315-2e5fbb493cdfLinearAlgebraStableRNGsGraphPlotupstream_cells_map$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_mapDicthboxBaseBase.Docs.HTML@html_strDiv=>$26191290-2b2d-43fe-b2bf-d690fd0bbe15precedence_heuristic cell_id$26191290-2b2d-43fe-b2bf-d690fd0bbe15downstream_cells_mapupstream_cells_map@md_strqa$dfe3dffd-926b-4083-9e66-8536e5df198dgetindex$e3ae5697-6b0b-4d5f-99a0-d579b6eff655precedence_heuristic cell_id$e3ae5697-6b0b-4d5f-99a0-d579b6eff655downstream_cells_mapupstream_cells_map@md_strgetindex$b18a3bf6-102e-49f5-af8c-f1c35d2e2a8bprecedence_heuristic cell_id$b18a3bf6-102e-49f5-af8c-f1c35d2e2a8bdownstream_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$95d7e9cd-b4a1-4205-b7d4-8c10916be8a2precedence_heuristic cell_id$95d7e9cd-b4a1-4205-b7d4-8c10916be8a2downstream_cells_mapstar$70296870-49af-4564-bdb7-bd2d49f9114bupstream_cells_maplength:star_n$0445aae6-2f7e-42b8-b30b-f31298cdeed0push!collectIntonessparse$884f9025-10e9-4657-88ec-55e6c9b6d530precedence_heuristic cell_id$884f9025-10e9-4657-88ec-55e6c9b6d530downstream_cells_mapupstream_cells_mapijkl2$fab75cf6-21cc-4001-84b4-9e66f55d5a6aviz$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166*cm$44a6b427-bd4b-4fa1-95d8-a8ea55719192precedence_heuristic cell_id$44a6b427-bd4b-4fa1-95d8-a8ea55719192downstream_cells_mapupstream_cells_map@md_strqa$dfe3dffd-926b-4083-9e66-8536e5df198dgetindex$dfe3dffd-926b-4083-9e66-8536e5df198dprecedence_heuristic cell_id$dfe3dffd-926b-4083-9e66-8536e5df198ddownstream_cells_mapqa$592510fd-a0e4-42e5-ae5b-cac301e74f0a$26191290-2b2d-43fe-b2bf-d690fd0bbe15$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_mapHTMLsprintHypertextLiteral.ResultHypertextLiteral$75597493-3e69-437f-9408-b43a89b35559HypertextLiteral.BypassHypertextLiteral.contentMarkdown@htl$04ea8b79-63ba-4eb4-938c-98a21668924aprecedence_heuristic cell_id$04ea8b79-63ba-4eb4-938c-98a21668924adownstream_cells_mapupstream_cells_map@md_strqa$dfe3dffd-926b-4083-9e66-8536e5df198dgetindex$dbef0e7d-b731-4d83-98e3-104b23f26042precedence_heuristic cell_id$dbef0e7d-b731-4d83-98e3-104b23f26042downstream_cells_mapn$2fe7f4eb-ca33-4338-ba8e-29b769b0dcceupstream_cells_map@md_strCore:Base.get@bindSliderBasePlutoRunnerPlutoRunner.create_bondCore.applicablegetindexcell_execution_orderU$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$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$fab75cf6-21cc-4001-84b4-9e66f55d5a6a$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$884f9025-10e9-4657-88ec-55e6c9b6d530$647c372e-c094-4dfc-8a48-7b7f93fb94dd$a413c12c-72c1-4f46-b7f2-0b0118c1b232$9b427766-5290-4dee-8dd5-5aab20080d0a$dfe3dffd-926b-4083-9e66-8536e5df198d$592510fd-a0e4-42e5-ae5b-cac301e74f0a$26191290-2b2d-43fe-b2bf-d690fd0bbe15$04ea8b79-63ba-4eb4-938c-98a21668924a$e721600c-1887-4e99-b474-a427b665e591$44a6b427-bd4b-4fa1-95d8-a8ea55719192$15cf368c-cada-4a72-b59b-a0f9dd0115b4$79910840-ec59-4433-bfb3-ae2d8da40d22last_hot_reload_timeshortpathsparse.jlprocess_statusreadypath8/home/runner/work/LINMA2472/LINMA2472/Lectures/sparse.jlpluto_versionv0.20.24last_save_timeAz'cell_orderU$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$e6697119-2801-48e2-b978-facc00af636d$33b368e7-d71e-40ff-8170-a18d11db98fc$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$884f9025-10e9-4657-88ec-55e6c9b6d530$fab75cf6-21cc-4001-84b4-9e66f55d5a6a$b33bf212-5f88-47ab-ba10-a2815d17f235$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-8536e5df198dpublished_objectsnbpkginstall_time_nsr instantiatedòinstalled_versionsGraphs1.13.1SparseMatrixColorings0.4.23Images0.26.2LinearAlgebrastdlibPlutoUI0.7.75SparseArraysstdlibHypertextLiteral0.9.5StableRNGs1.0.4GraphPlot0.6.2PlutoTeachingTools0.4.6terminal_outputsPlutoUIS Waiting for other notebooks to finish Pkg operations... === Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Manifest.toml` [14a3606d] ↑ MozillaCACerts_jll v2025.5.20 ⇒ v2025.11.4 Instantiating... === Precompiling... ===PlutoTeachingToolsS Waiting for other notebooks to finish Pkg operations... === Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Manifest.toml` [14a3606d] ↑ MozillaCACerts_jll v2025.5.20 ⇒ v2025.11.4 Instantiating... === Precompiling... ===GraphsS Waiting for other notebooks to finish Pkg operations... === Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Manifest.toml` [14a3606d] ↑ MozillaCACerts_jll v2025.5.20 ⇒ v2025.11.4 Instantiating... === Precompiling... ===LinearAlgebraS Waiting for other notebooks to finish Pkg operations... === Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Manifest.toml` [14a3606d] ↑ MozillaCACerts_jll v2025.5.20 ⇒ v2025.11.4 Instantiating... === Precompiling... ===StableRNGsS Waiting for other notebooks to finish Pkg operations... === Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Manifest.toml` [14a3606d] ↑ MozillaCACerts_jll v2025.5.20 ⇒ v2025.11.4 Instantiating... === Precompiling... ===ImagesS Waiting for other notebooks to finish Pkg operations... === Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Manifest.toml` [14a3606d] ↑ MozillaCACerts_jll v2025.5.20 ⇒ v2025.11.4 Instantiating... === Precompiling... ===SparseArraysS Waiting for other notebooks to finish Pkg operations... === Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Manifest.toml` [14a3606d] ↑ MozillaCACerts_jll v2025.5.20 ⇒ v2025.11.4 Instantiating... === Precompiling... ===GraphPlotS Waiting for other notebooks to finish Pkg operations... === Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Manifest.toml` [14a3606d] ↑ MozillaCACerts_jll v2025.5.20 ⇒ v2025.11.4 Instantiating... === Precompiling... ===SparseMatrixColoringsS Waiting for other notebooks to finish Pkg operations... === Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Manifest.toml` [14a3606d] ↑ MozillaCACerts_jll v2025.5.20 ⇒ v2025.11.4 Instantiating... === Precompiling... ===nbpkg_syncS Waiting for other notebooks to finish Pkg operations... === Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Manifest.toml` [14a3606d] ↑ MozillaCACerts_jll v2025.5.20 ⇒ v2025.11.4 Instantiating... === Precompiling... ===HypertextLiteralS Waiting for other notebooks to finish Pkg operations... === Resolving... ===  Project No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Project.toml`  Updating `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ppphbiqair/Manifest.toml` [14a3606d] ↑ MozillaCACerts_jll v2025.5.20 ⇒ v2025.11.4 Instantiating... === Precompiling... ===enabled÷restart_recommended_msgrestart_required_msgbusy_packageswaiting_for_permission,waiting_for_permission_but_probably_disabled«cell_inputsU$a5769449-96cd-477a-bceb-ad9439a37430cell_id$a5769449-96cd-477a-bceb-ad9439a37430codemd""" # 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) """metadatashow_logsèdisabled®skip_as_script«code_folded$a4ecf92d-6c45-4112-8f0c-06a6d227cd84cell_id$a4ecf92d-6c45-4112-8f0c-06a6d227cd84codemd"""## 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. """metadatashow_logsèdisabled®skip_as_script«code_folded$f29078e8-242a-4b88-881f-781829c16ed5cell_id$f29078e8-242a-4b88-881f-781829c16ed5codeْmd"Taken from a tutorial of the [SparseMatrixColorings' doc](https://gdalle.github.io/SparseMatrixColorings.jl/stable/tutorial/#Coloring-results)"metadatashow_logsèdisabled®skip_as_script«code_folded$91226321-fc72-4bd9-8d78-9c2bff5c760acell_id$91226321-fc72-4bd9-8d78-9c2bff5c760acodeRviz(S, structure = :nonsymmetric, decompression = :direct, plot_size = (3cm, 3cm))metadatashow_logsèdisabled®skip_as_script«code_folded$6c174bac-faef-424a-9de7-e4c7be8ddb27cell_id$6c174bac-faef-424a-9de7-e4c7be8ddb27code0md"## Larger example : star vs acyclic coloring"metadatashow_logsèdisabled®skip_as_script«code_folded$2728dc2c-ca17-4989-9259-451f95a24bd2cell_id$2728dc2c-ca17-4989-9259-451f95a24bd2codesbegin 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 endmetadatashow_logsèdisabled®skip_as_script«code_folded$a413c12c-72c1-4f46-b7f2-0b0118c1b232cell_id$a413c12c-72c1-4f46-b7f2-0b0118c1b232codeSviz(large, decompression = :direct, structure = :symmetric, plot_size = (6cm, 6cm))metadatashow_logsèdisabled®skip_as_script«code_folded$79910840-ec59-4433-bfb3-ae2d8da40d22cell_id$79910840-ec59-4433-bfb3-ae2d8da40d22codeqa(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. """)metadatashow_logsèdisabled®skip_as_script«code_folded$874b6593-7310-4788-beb0-2f18c0ca09a7cell_id$874b6593-7310-4788-beb0-2f18c0ca09a7code$md"## Three columns in just one JVP"metadatashow_logsèdisabled®skip_as_script«code_folded$9e24f674-42af-4fa8-bf3e-42e14d855a58cell_id$9e24f674-42af-4fa8-bf3e-42e14d855a58codetwo_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), )metadatashow_logsèdisabled®skip_as_script«code_folded$3e6fc4af-19f4-4ff9-b9cf-759e831ff2a4cell_id$3e6fc4af-19f4-4ff9-b9cf-759e831ff2a4codesviz(SparseMatrixColorings.what_fig_41().A, decompression = :direct, structure = :symmetric, plot_size = (5cm, 5cm))metadatashow_logsèdisabled®skip_as_script«code_folded$2bd9ea13-362e-47ac-b26d-8e36d33e04eacell_id$2bd9ea13-362e-47ac-b26d-8e36d33e04eacode٤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."metadatashow_logsèdisabled®skip_as_script«code_folded$b33bf212-5f88-47ab-ba10-a2815d17f235cell_id$b33bf212-5f88-47ab-ba10-a2815d17f235code"md""" ## 2 colors with substitutions 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} ``` """metadatashow_logsèdisabled®skip_as_script«code_folded$d5b7f51b-e451-40a7-aa41-a8006decba33cell_id$d5b7f51b-e451-40a7-aa41-a8006decba33codeXmd"""## 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. """metadatashow_logsèdisabled®skip_as_script«code_folded$0a91e27f-3cea-415e-aed4-123482da375acell_id$0a91e27f-3cea-415e-aed4-123482da375acodemd"Simple [operator overloading implementation](https://adrianhill.de/SparseConnectivityTracer.jl/dev/internals/how_it_works/)"metadatashow_logsèdisabled®skip_as_script«code_folded$2e3cdd4b-9d04-477c-8c6a-fec6ec846919cell_id$2e3cdd4b-9d04-477c-8c6a-fec6ec846919codeمxtracer = [ MyGradientTracer(Set(1)), MyGradientTracer(Set(2)), MyGradientTracer(Set(3)), MyGradientTracer(Set(4)), ]metadatashow_logsèdisabled®skip_as_script«code_folded$4da92dbb-fcbd-4991-a2f1-f866778a27efcell_id$4da92dbb-fcbd-4991-a2f1-f866778a27efcodemd"## Utils"metadatashow_logsèdisabled®skip_as_script«code_folded$33b368e7-d71e-40ff-8170-a18d11db98fccell_id$33b368e7-d71e-40ff-8170-a18d11db98fccodeRviz(ijkl, decompression = :direct, structure = :symmetric, plot_size = (3cm, 3cm))metadatashow_logsèdisabled®skip_as_script«code_folded$647c372e-c094-4dfc-8a48-7b7f93fb94ddcell_id$647c372e-c094-4dfc-8a48-7b7f93fb94ddcodeXviz(ijkl, decompression = :substitution, structure = :symmetric, plot_size = (4cm, 4cm))metadatashow_logsèdisabled®skip_as_script«code_folded$7fec005c-11b9-4a75-a93c-195d456db190cell_id$7fec005c-11b9-4a75-a93c-195d456db190codemd"## Scalar example"metadatashow_logsèdisabled®skip_as_script«code_folded$6bd04f2f-ed5f-4ecf-91dd-8868ec5b83e1cell_id$6bd04f2f-ed5f-4ecf-91dd-8868ec5b83e1code1using SparseArrays, Images, SparseMatrixColoringsmetadatashow_logsèdisabled®skip_as_script«code_folded$2578b84a-365a-47b6-b58f-1696517c5d02cell_id$2578b84a-365a-47b6-b58f-1696517c5d02codemd""" # 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 """metadatashow_logsèdisabled®skip_as_script«code_folded$fab75cf6-21cc-4001-84b4-9e66f55d5a6acell_id$fab75cf6-21cc-4001-84b4-9e66f55d5a6acode8ijkl2 = sparse([ 1 2 0 0 2 3 4 0 0 4 5 6 0 0 6 7 ]);metadatashow_logsèdisabled®skip_as_script«code_folded$29d9f355-26aa-4714-9f9e-3d020016662ecell_id$29d9f355-26aa-4714-9f9e-3d020016662ecodemd"## Small Example"metadatashow_logsèdisabled®skip_as_script«code_folded$e3dec4ca-69c0-4955-9303-5f8a239546f2cell_id$e3dec4ca-69c0-4955-9303-5f8a239546f2code_md"Let ``h_c`` be the sum of the columns of ``B_c`` hence the result of the corresponding HVP."metadatashow_logsèdisabled®skip_as_script«code_folded$285d3797-5086-4adc-839c-2204128585e1cell_id$285d3797-5086-4adc-839c-2204128585e1codeomd""" * For any pink node ``u > 1``, the offdiagonal entry ``a_{u,1}`` can be obtained from the yellow HVP. """metadatashow_logsèdisabled®skip_as_script«code_folded$0445aae6-2f7e-42b8-b30b-f31298cdeed0cell_id$0445aae6-2f7e-42b8-b30b-f31298cdeed0codeFmd"`n` = $(@bind star_n Slider(3:10, default = 6, show_value = true))"metadatashow_logsèdisabled®skip_as_script«code_folded$5a6aec48-54fb-4d88-a8a1-b06a2bb99108cell_id$5a6aec48-54fb-4d88-a8a1-b06a2bb99108codeOS = 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 ])metadatashow_logsèdisabled®skip_as_script«code_folded$c2e4982a-3798-4c45-8831-5a76b3b29f6ecell_id$c2e4982a-3798-4c45-8831-5a76b3b29f6ecodemd"[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."metadatashow_logsèdisabled®skip_as_script«code_folded$75597493-3e69-437f-9408-b43a89b35559cell_id$75597493-3e69-437f-9408-b43a89b35559codeOusing PlutoUI, PlutoUI.ExperimentalLayout, HypertextLiteral, PlutoTeachingToolsmetadatashow_logsèdisabled®skip_as_script«code_folded$1efb0f40-fb9e-4e5b-be59-84910afbf376cell_id$1efb0f40-fb9e-4e5b-be59-84910afbf376codemd""" ## 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) ``` """metadatashow_logsèdisabled®skip_as_script«code_folded$1167ae71-b63d-4ccc-a120-31c8483eca85cell_id$1167ae71-b63d-4ccc-a120-31c8483eca85codeytracer = f(xtracer)metadatashow_logsèdisabled®skip_as_script«code_folded$19dd6563-1a4e-479f-881d-9bcbc720ea36cell_id$19dd6563-1a4e-479f-881d-9bcbc720ea36codezmd""" # What color is your Hessian ? How many HVP do we need to find the values of this sparse **symmetric** matrix ? """metadatashow_logsèdisabled®skip_as_script«code_folded$e882ebee-36ad-43d9-8ab7-20f7e8b2d9fecell_id$e882ebee-36ad-43d9-8ab7-20f7e8b2d9fecodeUmd""" ## Example Consider the following sparsity pattern of the Jacobian matrix: """metadatashow_logsèdisabled®skip_as_script«code_folded$cabeb42c-f40b-4549-b9a2-3bda7a988672cell_id$cabeb42c-f40b-4549-b9a2-3bda7a988672codeimg("Gebremedhin_Figure_6_1")metadatashow_logsèdisabled®skip_as_script«code_folded$a7e8569e-2fed-4069-aa84-ced67849ab15cell_id$a7e8569e-2fed-4069-aa84-ced67849ab15code'md"## The same applies to reverse mode"metadatashow_logsèdisabled®skip_as_script«code_folded$e721600c-1887-4e99-b474-a427b665e591cell_id$e721600c-1887-4e99-b474-a427b665e591codeqa(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}``. """)metadatashow_logsèdisabled®skip_as_script«code_folded$e9135060-75d4-4f5a-9315-2e5fbb493cdfcell_id$e9135060-75d4-4f5a-9315-2e5fbb493cdfcodeLfunction 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) gp = gplot(Graphs.SimpleDiGraph(S - Diagonal(diag(S))); nodefillc = colorscheme[result.color], kws...) A_img, gp, B_img endmetadatashow_logsèdisabled®skip_as_script«code_folded$d46dcdb3-ac4c-4ba9-ac48-6d6a693630d3cell_id$d46dcdb3-ac4c-4ba9-ac48-6d6a693630d3code$f(x) = x[1] + x[2]*x[3] * sign(x[4])metadatashow_logsèdisabled®skip_as_script«code_folded$a546edb2-6a72-4c5f-95f7-cc7709bbb505cell_id$a546edb2-6a72-4c5f-95f7-cc7709bbb505codeF(xtracer)metadatashow_logsèdisabled®skip_as_script«code_folded$f8e9d672-e6ad-4910-8307-2b56616b11bccell_id$f8e9d672-e6ad-4910-8307-2b56616b11bccodeQBase.sign(x::MyGradientTracer) = MyGradientTracer(Set()) # return empty index setmetadatashow_logsèdisabled®skip_as_script«code_folded$22c1030b-bef5-4af5-9d5f-6afb4a7ae699cell_id$22c1030b-bef5-4af5-9d5f-6afb4a7ae699code!img("Gebremedhin_Figure_6_1_mat")metadatashow_logsèdisabled®skip_as_script«code_folded$18594f1f-6036-4a95-8682-cf415c998311cell_id$18594f1f-6036-4a95-8682-cf415c998311code$md"# Sparsity detection of Jacobian"metadatashow_logsèdisabled®skip_as_script«code_folded$dc23180e-2b0f-41ae-aebf-0159a8f8677acell_id$dc23180e-2b0f-41ae-aebf-0159a8f8677acodeltwo_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), )metadatashow_logsèdisabled®skip_as_script«code_folded$2fe7f4eb-ca33-4338-ba8e-29b769b0dccecell_id$2fe7f4eb-ca33-4338-ba8e-29b769b0dccecodeElarge = sparse(Symmetric(sprand(StableRNG(0), Bool, n, n, 0.2) + I));metadatashow_logsèdisabled®skip_as_script«code_folded$97c94c5a-fab5-4226-b803-10c85a298f2acell_id$97c94c5a-fab5-4226-b803-10c85a298f2acode2struct MyGradientTracer indexset::Set{Int} endmetadatashow_logsèdisabled®skip_as_script«code_folded$1617c79d-3abe-4ffc-9ee1-3312f2b28eb5cell_id$1617c79d-3abe-4ffc-9ee1-3312f2b28eb5codemd""" ## 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) """metadatashow_logsèdisabled®skip_as_script«code_folded$8e2045f3-ee09-4439-b504-d2ca9f58a3ddcell_id$8e2045f3-ee09-4439-b504-d2ca9f58a3ddcodecBase.:+(a::MyGradientTracer, b::MyGradientTracer) = MyGradientTracer(union(a.indexset, b.indexset))metadatashow_logsèdisabled®skip_as_script«code_folded$f2418632-3261-4acb-8cc6-df333b5480a5cell_id$f2418632-3261-4acb-8cc6-df333b5480a5codemd"## Illustrative example"metadatashow_logsèdisabled®skip_as_script«code_folded$d0ba0c62-c788-4871-959c-fe7044519849cell_id$d0ba0c62-c788-4871-959c-fe7044519849codemd""" # Less colors but nontrivial substitution ```math \begin{bmatrix} a_{1} & a_{2} & &\\ a_2 & a_3 & a_4 &\\ & a_4 & a_5 & a_6\\ & & a_6 & a_7 \end{bmatrix} ``` With star coloring, 3 colors: """metadatashow_logsèdisabled®skip_as_script«code_folded$592510fd-a0e4-42e5-ae5b-cac301e74f0acell_id$592510fd-a0e4-42e5-ae5b-cac301e74f0acodeEqa(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. """)metadatashow_logsèdisabled®skip_as_script«code_folded$5892dfbb-b375-407b-a0a7-da66adb71b67cell_id$5892dfbb-b375-407b-a0a7-da66adb71b67codemd""" [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. [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``. """metadatashow_logsèdisabled®skip_as_script«code_folded$fa2a8104-2a3f-438c-bc63-4236a9f5ebebcell_id$fa2a8104-2a3f-438c-bc63-4236a9f5ebebcodecBase.:*(a::MyGradientTracer, b::MyGradientTracer) = MyGradientTracer(union(a.indexset, b.indexset))metadatashow_logsèdisabled®skip_as_script«code_folded$aeb8b749-006a-400f-9b7d-05333fd7214fcell_id$aeb8b749-006a-400f-9b7d-05333fd7214fcode%md"## Whole Jacobian in just two JVP"metadatashow_logsèdisabled®skip_as_script«code_folded$32440932-322a-46ce-911d-5fa6a1136bcacell_id$32440932-322a-46ce-911d-5fa6a1136bcacode6ijkl = sparse([ 1 2 3 0 2 4 0 5 3 0 6 0 0 5 0 7 ])metadatashow_logsèdisabled®skip_as_script«code_folded$e6697119-2801-48e2-b978-facc00af636dcell_id$e6697119-2801-48e2-b978-facc00af636dcodemd""" ## Need 3 colors for a path of 4 vertices ```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} ``` """metadatashow_logsèdisabled®skip_as_script«code_folded$352c92ec-14da-4beb-85c4-f66d77fa42d6cell_id$352c92ec-14da-4beb-85c4-f66d77fa42d6codesimg("https://iclr-blogposts.github.io/2025/assets/img/2025-04-28-sparse-autodiff/compute_graph.png", :width => 330)metadatashow_logsèdisabled®skip_as_script«code_folded$21898d8d-f822-4128-ad56-d9a10865fb1dcell_id$21898d8d-f822-4128-ad56-d9a10865fb1dcode٨three_columns(left, center, right) = hbox([ left, Div(html" ", style = Dict("flex-grow" => "1")), center, Div(html" ", style = Dict("flex-grow" => "1")), right, ])metadatashow_logsèdisabled®skip_as_script«code_folded$39e06fde-d734-11f0-a308-89fba7e8abd6cell_id$39e06fde-d734-11f0-a308-89fba7e8abd6codeٻ@htl("""

Sparse AD

Benoît Legat

$(PlutoTeachingTools.ChooseDisplayMode()) $(PlutoUI.TableOfContents(depth=1)) """)metadatashow_logsèdisabled®skip_as_script«code_folded$726208c6-e856-42a2-b027-555388bc505ecell_id$726208c6-e856-42a2-b027-555388bc505ecodetwo_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"), )metadatashow_logsèdisabled®skip_as_script«code_folded$12ffe7c2-2bf6-4949-ae28-f3d8e03a5da5cell_id$12ffe7c2-2bf6-4949-ae28-f3d8e03a5da5codeZtwo_columns( md"Color's columns are structurally orthogonal", md"Jacobian from 3 JVP", )metadatashow_logsèdisabled®skip_as_script«code_folded$9df9c76a-48af-4ca6-83f1-b8798d6d4e34cell_id$9df9c76a-48af-4ca6-83f1-b8798d6d4e34code+Base.:/(a::MyGradientTracer, b::Number) = ametadatashow_logsèdisabled®skip_as_script«code_folded$76162106-fb90-4883-b2d2-b87e1419c072cell_id$76162106-fb90-4883-b2d2-b87e1419c072code,md""" ## Formulation as coloring problem """metadatashow_logsèdisabled®skip_as_script«code_folded$760ef943-e9d9-4cdc-8977-932cf6fcb78acell_id$760ef943-e9d9-4cdc-8977-932cf6fcb78acodemd"## Coloring of a star"metadatashow_logsèdisabled®skip_as_script«code_folded$a01688ec-8f16-4d39-b39d-6d1acd24d7adcell_id$a01688ec-8f16-4d39-b39d-6d1acd24d7adcodetwo_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), )metadatashow_logsèdisabled®skip_as_script«code_folded$a3bf5961-323b-4adc-99a0-9a456a0bfd48cell_id$a3bf5961-323b-4adc-99a0-9a456a0bfd48code2F(x) = [x[1]*x[2]+sign(x[3]), sign(x[3]) * x[4]/2]metadatashow_logsèdisabled®skip_as_script«code_folded$d23e7238-5edb-42d3-96d9-0dffa9e7f326cell_id$d23e7238-5edb-42d3-96d9-0dffa9e7f326codeٲ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)))", ])metadatashow_logsèdisabled®skip_as_script«code_folded$a7b85908-404b-475b-9875-c1190de5ff71cell_id$a7b85908-404b-475b-9875-c1190de5ff71code>md""" * Each off-diagonal entry ``a_{uv}`` corresponds to an edge in the graph. * The edge links nodes ``u, v`` of 2 different colors ``\phi(u)`` and ``\phi(v)`` * If ``u`` is not adjacent to any other nodes of color ``\phi(v)`` then ``a_{uv}`` is the **only term** at the row ``u`` of the HVP of color ``\phi(v)`` """metadatashow_logsèdisabled®skip_as_script«code_folded$15cf368c-cada-4a72-b59b-a0f9dd0115b4cell_id$15cf368c-cada-4a72-b59b-a0f9dd0115b4codeqa( 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}`` """, )metadatashow_logsèdisabled®skip_as_script«code_folded$70296870-49af-4564-bdb7-bd2d49f9114bcell_id$70296870-49af-4564-bdb7-bd2d49f9114bcodeRviz(star, decompression = :direct, structure = :symmetric, plot_size = (5cm, 5cm))metadatashow_logsèdisabled®skip_as_script«code_folded$45f4edeb-d934-413f-9f45-568465111b6ecell_id$45f4edeb-d934-413f-9f45-568465111b6ecode/md"## Sparsity detection with multiple outputs"metadatashow_logsèdisabled®skip_as_script«code_folded$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166cell_id$dcf92bc9-5e0f-4716-bb07-ca0d9b73b166codeGviz(args...; kws...) = three_columns(colored_plots(args...; kws...)...)metadatashow_logsèdisabled®skip_as_script«code_folded$9b427766-5290-4dee-8dd5-5aab20080d0acell_id$9b427766-5290-4dee-8dd5-5aab20080d0acodeYviz(large, decompression = :substitution, structure = :symmetric, plot_size = (6cm, 6cm))metadatashow_logsèdisabled®skip_as_script«code_folded$4f8de444-dcb4-411a-b087-6948699614e0cell_id$4f8de444-dcb4-411a-b087-6948699614e0code2using Graphs, GraphPlot, LinearAlgebra, StableRNGsmetadatashow_logsèdisabled®skip_as_script«code_folded$e820e135-2df2-4fa3-a09b-8ce7e5a1f745cell_id$e820e135-2df2-4fa3-a09b-8ce7e5a1f745codedtwo_columns(left, right) = hbox([ left, Div(html" ", style = Dict("flex-grow" => "1")), right, ])metadatashow_logsèdisabled®skip_as_script«code_folded$26191290-2b2d-43fe-b2bf-d690fd0bbe15cell_id$26191290-2b2d-43fe-b2bf-d690fd0bbe15codeqa(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. """)metadatashow_logsèdisabled®skip_as_script«code_folded$e3ae5697-6b0b-4d5f-99a0-d579b6eff655cell_id$e3ae5697-6b0b-4d5f-99a0-d579b6eff655codemd"""## 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. """metadatashow_logsèdisabled®skip_as_script«code_folded$b18a3bf6-102e-49f5-af8c-f1c35d2e2a8bcell_id$b18a3bf6-102e-49f5-af8c-f1c35d2e2a8bcodeemd"The sign function is constant over ``x > 0`` and ``x < 0`` so its output carries **no** variables"metadatashow_logsèdisabled®skip_as_script«code_folded$e2eb1894-06ad-47a0-9ee0-c65b24a669b5cell_id$e2eb1894-06ad-47a0-9ee0-c65b24a669b5code\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) """metadatashow_logsèdisabled®skip_as_script«code_folded$95d7e9cd-b4a1-4205-b7d4-8c10916be8a2cell_id$95d7e9cd-b4a1-4205-b7d4-8c10916be8a2codeٱ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;metadatashow_logsèdisabled®skip_as_script«code_folded$884f9025-10e9-4657-88ec-55e6c9b6d530cell_id$884f9025-10e9-4657-88ec-55e6c9b6d530codeSviz(ijkl2, decompression = :direct, structure = :symmetric, plot_size = (3cm, 3cm))metadatashow_logsèdisabled®skip_as_script«code_folded$44a6b427-bd4b-4fa1-95d8-a8ea55719192cell_id$44a6b427-bd4b-4fa1-95d8-a8ea55719192codeqa(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``. """)metadatashow_logsèdisabled®skip_as_script«code_folded$dfe3dffd-926b-4083-9e66-8536e5df198dcell_id$dfe3dffd-926b-4083-9e66-8536e5df198dcodebegin function qa(question, answer) return @htl("
$question$answer
") end function _inline_html(m::Markdown.Paragraph) return sprint(Markdown.htmlinline, m.content) end function qa(question::Markdown.MD, answer) # `html(question)` will create `

` 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 endmetadatashow_logsèdisabled®skip_as_script«code_folded$04ea8b79-63ba-4eb4-938c-98a21668924acell_id$04ea8b79-63ba-4eb4-938c-98a21668924acoderqa(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. """)metadatashow_logsèdisabled®skip_as_script«code_folded$dbef0e7d-b731-4d83-98e3-104b23f26042cell_id$dbef0e7d-b731-4d83-98e3-104b23f26042codeCmd"`n` = $(@bind n Slider(10:20, show_value = true, default = 16))"metadatashow_logsèdisabled®skip_as_script«code_foldedënotebook_id$57dae392-3e1c-11f1-9beb-bb91620c80b9in_temp_dir¨metadata