3f:null 40:["$","title",null,{"children":"Gauss-Jordan elimination for sparse matrices over GF(2) | Maxim Taldykin | Observable"}] 46:[] 44:{"id":"db1205cbc3d6202c","slug":"gauss-jordan","title":"Gauss-Jordan elimination for sparse matrices over GF(2)","thumbnail":"ee7f7509c6dfce8659d45da1491b7511f91efb99dca05fb49b86718542dc9116","access_level":"public","create_time":"$D2023-04-23T20:37:36.604Z","update_time":"$D2023-04-25T10:48:05.259Z","view_time":null,"first_public_time":"$D2023-04-23T20:37:36.604Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"bdbed6e4505e8e57","login":"jorpic","name":"Maxim Taldykin","avatar_url":"https://avatars-next.observableusercontent.com/93d22477a947653107265a9d66c0181885f639e1105a3ec050197357579ed48b","tier":"starter_2024","bio":"","following":false},"version":152,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"cb02791459828809","login":"jorpic","name":"Maxim Taldykin","avatar_url":"https://avatars-next.observableusercontent.com/93d22477a947653107265a9d66c0181885f639e1105a3ec050197357579ed48b","tier":null,"bio":"","following":false}],"members":[{"type":"individual","id":"cb02791459828809","login":"jorpic","name":"Maxim Taldykin","avatar_url":"https://avatars-next.observableusercontent.com/93d22477a947653107265a9d66c0181885f639e1105a3ec050197357579ed48b","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Gauss-Jordan elimination for sparse matrices over GF(2)","cells":[{"id":0,"value":"# Gauss-Jordan elimination for sparse matrices over GF(2)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":5,"value":"function add(xs, ys) {\n // assume that xs and ys are sorted\n const zs = [];\n let i = 0, j = 0;\n while(i < xs.length && j < ys.length) {\n const x = xs[i], y = ys[j];\n if(x < y) {\n zs.push(x);\n i++;\n }\n else if(y < x) {\n zs.push(y);\n j++;\n } else {\n i++;\n j++;\n }\n }\n // only one of this loop will be evaluated because i == |xs| or j == |ys|\n while(i < xs.length) zs.push(xs[i++]);\n while(j < ys.length) zs.push(ys[j++]);\n return zs;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"[[[0,1,2], [0,1,2]]\n,[[0,1,2], [2,3]]\n,[[0,4,5], [0,2,3]]\n,[[2,3,4], [5,6,7]]\n].map(([xs, ys]) => ({xs, ys, zs: add(xs, ys)}))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"function toRowEchelon(eqs, stepLimit) {\n eqs = structuredClone(eqs)\n // Assume that each equation is an ordered array.\n for(let m = 0; m < eqs.length; m++) {\n if(eqs[m].length == 0) continue;\n\n // Search a pivot (the row with the leftmost non-zero coefficient) among rows [m...].\n let pivot = null;\n for(let i = m; i < eqs.length; i++) {\n if(eqs[i].length > 0 && (pivot == null || eqs[i][0] < pivot.val)) {\n pivot = {val: eqs[i][0], i};\n }\n }\n if(pivot == null) break;\n // Update the current row if it does not contain pivot var.\n if(pivot.i != m && eqs[m][0] != pivot.val) {\n if(stepLimit !== undefined && --stepLimit <= 0) return eqs;\n eqs[m] = add(eqs[m], eqs[pivot.i]); \n }\n \n for(let i = 0; i < eqs.length; i++) {\n if(i !== m && eqs[i].includes(pivot.val)) {\n if(stepLimit !== undefined && --stepLimit <= 0) return eqs;\n eqs[i] = add(eqs[i], eqs[m]); \n }\n }\n }\n return eqs.filter(eq => eq.length > 0);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"function range(min, max) {\n return Array(max - min).fill(0).map((_,i) => i+min);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":25,"value":"range(5,13)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"function plotSystem(sys, nVars=null, nEqs=null) {\n const sysData = [];\n const vars = [...varSet(sys)].sort();\n const var2ix = vars.reduce((r, v, i) => { r[v] = i; return r;}, {});\n const eqs = sys.map(eq => eq.map(v => v)); //var2ix\n const plotData = [].concat.apply([], eqs.map((eq, y) => eq.map(x => ({x,y}))));\n\n return Plot.plot({\n x: {axis: null}, //, domain: range(0, nVars || vars.length)},\n y: {axis: null}, //, domain: range(0, nEqs || sys.length)},\n tooltip: {fill: \"coral\", stroke: \"coral\"},\n marks: [\n Plot.cell(plotData, {x: \"x\", y: \"y\", fill: _ => \"lightblue\", title: d => d.x}),\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":87,"value":"tests = [\n [[15,20,25],[15,36,39],[20,48,52],[25,60,65],[36,48,60],[39,52,65]],\n [[48,64,80],[48,90,102],[54,72,90],[54,240,246],[64,120,136],[72,320,328],[80,150,170],[90,120,150],[90,216,234],[90,400,410],[90,672,678],[102,136,170],[120,288,312],[120,896,904],[150,360,390],[150,1120,1130],[216,288,360],[216,960,984],[234,312,390],[234,1040,1066],[240,320,400],[246,328,410],[400,960,1040],[410,984,1066],[672,896,1120],[678,904,1130]],\n [[162,216,270],[162,720,738],[162,2184,2190],[216,960,984],[216,2912,2920],[270,1200,1230],[270,3640,3650],[720,960,1200],[738,984,1230],[2184,2912,3640],[2190,2920,3650]],\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":111,"value":"viewof sys = Inputs.range([0, tests.length-1], {value: 0, step: 1, label: \"test id\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":128,"value":"viewof steps = Inputs.range([0, 1000], {value: 0, step: 1, label: \"iteration\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"before = plotSystem(tests[sys])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":139,"value":"\n \n \n \n

${before}

${after}

\n \n","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":89,"value":"after = plotSystem(toRowEchelon(tests[sys], steps))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"function varSet(eqs) {\n const vars = new Set();\n eqs.forEach(eq => eq.forEach(v => vars.add(v)));\n return vars;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":34,"value":"varSet([[10,30],[0,2,3]])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":66,"value":"import {Plot} from \"@mkfreeman/plot-tooltip\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W46","stdlib":"1"}} 45:"$44:body"