2c:null 2d:["$","title",null,{"children":"Time–time complexity of matrix multiplication | Toph Tucker | Observable"}] 32:Tf4e,const margin3d = {top: 40, right: 0, left: 110, bottom: 40}; const vbX = minX3d - margin3d.left; const vbY = minY3d - margin3d.top; const vbW = (maxX3d - minX3d) + margin3d.left + margin3d.right; const vbH = (maxY3d - minY3d) + margin3d.top + margin3d.bottom; // a few light gridlines on the floor (t = 0) to help read the 3D space: // one line per year-tick running across n, plus two lines running along // the depth (z) axis at the near and far edges of the n range. const zNear = zScaleYear(yearsExtent3d[1]); // most recent year, front const zFar = zFor(null); // naive, arbitrarily further back than the earliest year const yearTicks3d = zScaleYear.ticks(8); const nGridLines3d = yearTicks3d.map(year => { const Z = zScaleYear(year); return {year, p0: project3d(0, 0, Z), p1: project3d(99, 0, Z)}; }); const zGridLines3d = [0, 99].map(n => ({ p0: project3d(n, 0, zFar), p1: project3d(n, 0, zNear) })); // ---- axis-arrow annotations ---- // The three axes of the 3D projection are: // - n (input size), which points (cos, sin) of angle3d: down-and-right // - t (processing time), which points straight up (0, -1) // - year/Z ("researcher time"), which points (-cos, sin) of angle3d: down-and-left const axisArrowLen = 40; const unitN3d = [Math.cos(angle3d), Math.sin(angle3d)]; const unitZ3d = [-Math.cos(angle3d), Math.sin(angle3d)]; const unitT3d = [0, -1]; function makeAxisArrow(base, unit, len = axisArrowLen) { const tail = base; const tip = [base[0] + unit[0] * len, base[1] + unit[1] * len]; return {tail, tip}; } const arrowOrigin = [maxX3d - 140, maxY3d - 40]; const researcherArrow = makeAxisArrow(arrowOrigin, unitZ3d); const inputArrow = makeAxisArrow(arrowOrigin, unitN3d); const processingArrow = makeAxisArrow(arrowOrigin, unitT3d); display(svg``); 33:T439,// simple orthographic (isometric-style) projection: // X = size n (left-right), Y = time t (up-down), Z = year (depth, into the screen) const angle3d = Math.PI / 6; // 30° const nScale3d = d3.scaleLinear([0, 99], [0, 480]); const tScale3d = d3.scaleLinear([0, 400000], [0, 260]); // Z is proportional to actual year, like a real linear axis. Increasing Z // pushes points down-and-left, which reads as "nearer the viewer", so more // recent years get larger Z (in front); "naive" has no year, so it's placed // an arbitrary bit further back than the earliest year (i.e. an even smaller Z). const pxPerYear = 24; const yearsExtent3d = d3.extent(data, d => d.year); const zScaleYear = d3.scaleLinear(yearsExtent3d, [0, (yearsExtent3d[1] - yearsExtent3d[0]) * pxPerYear]); const naiveExtraGap = 130; function zFor(year) { return year === null ? zScaleYear(yearsExtent3d[0]) - naiveExtraGap : zScaleYear(year); } function project3d(n, t, Z) { const X = nScale3d(n); const Y = tScale3d(t); return [ (X - Z) * Math.cos(angle3d), (X + Z) * Math.sin(angle3d) - Y ]; }34:[] 30:{"id":"567edadfb4ec4a77","slug":"time-time-complexity-of-matrix-multiplication","title":"Time–time complexity of matrix multiplication","thumbnail":"797b8caf2706aceb502546f7c19b2abdeb9da067b74cb35ebe8102da4c8de9c1","access_level":"public","create_time":"$D2026-08-19T01:57:23.312Z","update_time":"$D2026-08-19T03:54:00.551Z","view_time":null,"first_public_time":"$D2026-08-19T03:43:06.494Z","fork":false,"stars":4,"starred":false,"owner":{"type":"team","id":"97290e936c339d8e","login":"tophtucker","name":"Toph Tucker","avatar_url":"https://avatars-next.observableusercontent.com/3706c31a8f9c59bb716c022c04b9c073144cd1368b78ac85f49139be6c93c34e","tier":"pro_2024"},"version":264,"publish_version":264,"role":null,"authored":false,"authors":[{"type":"individual","id":"0bb2842b01e0c652","login":"tophtucker","name":"Toph Tucker","avatar_url":"https://avatars-next.observableusercontent.com/3706c31a8f9c59bb716c022c04b9c073144cd1368b78ac85f49139be6c93c34e","tier":null}],"members":[{"type":"individual","id":"0bb2842b01e0c652","login":"tophtucker","name":"Toph Tucker","avatar_url":"https://avatars-next.observableusercontent.com/3706c31a8f9c59bb716c022c04b9c073144cd1368b78ac85f49139be6c93c34e","tier":null,"role":"editor"},{"type":"team","id":"97290e936c339d8e","login":"tophtucker","name":"Toph Tucker","avatar_url":"https://avatars-next.observableusercontent.com/3706c31a8f9c59bb716c022c04b9c073144cd1368b78ac85f49139be6c93c34e","tier":"pro_2024","role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"subscribed":null,"forks":1,"collection":{"id":"ee48d2d87f751f74","slug":"sketches","title":"Sketches","owner":{"id":"97290e936c339d8e","login":"tophtucker","name":"Toph Tucker"}},"type":"notebook","body":{"title":"Time–time complexity of matrix multiplication","cells":[{"id":16,"value":"# Time–time complexity of matrix multiplication\n\nThe “[time complexity](https://en.wikipedia.org/wiki/Time_complexity)” of an algorithm describes how long it takes to run for inputs of different sizes. Its slope is like the speed at which the algorithm gets slower in the worst-case scenario.\n\nSometimes many algorithms perform the same task, such as matrix multiplication. Over time, we’ve discovered faster and faster ways to do it:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":17,"value":"\n \n ${data.map(d => html``)}\n \n

${d.year}

${d.researcher ?? \"Naïve\"}

${tex`O(n^{${d.exponent}})`}

","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"},{"id":1,"value":"The most recent improvement was published, at time of writing, [yesterday](https://arxiv.org/abs/2608.16884v1).\n\nIf you think of the scientific discovery process as itself a kind of algorithm, then you could say it, too, has a kind of “time complexity”, which describes how fast the task gets faster over time as people discover better ways to do it.\n\nSo the “time–time complexity of matrix multiplication” refers to the curve describing how fast «the curve describing how fast matrix multiplication gets slower» gets faster.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":12,"value":"$32","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined"},{"id":19,"value":"I’m cheating, or just gesturing at something; I have not defined the worst- or best-case asymptotic behavior of the researchers with some limiting function. I’ve only drawn a few samples.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":14,"value":"const checkbox = html``\nconst includeBinet = Generators.input(checkbox);\ndisplay(md`The “naïve” method of matrix multiplication, here placed arbitrarily without a real date, in fact [dates back to](https://en.wikipedia.org/wiki/Matrix_multiplication) Jacques Philippe Marie Binet in 1812. But if we were to ${checkbox} include him, the scale would be so blown out as to render the graphic illegible at laptop-screen scale.`)","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined"},{"id":20,"value":"For more, see:\n\n- Wikipedia, “[Computational complexity of matrix multiplication](https://en.wikipedia.org/wiki/Computational_complexity_of_matrix_multiplication)”\n- Eric Weisstein, “[Strassen Formulas](https://mathworld.wolfram.com/StrassenFormulas.html)”\n- Scott Aaronson, “[2.373](https://scottaaronson.blog/?p=839)”, 2011\n- David Bau, “[Omega Improved](https://davidbau.com/archives/2011/12/10/omega_improved.html)”, 2011","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":13,"value":"---\n## Appendix","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":2,"value":"const data = d3.csvParse(\n `year,researcher,exponent\n${includeBinet ? \"1812,Binet,3\" : \",,3\"}\n1969,Strassen,2.808\n1978,Pan,2.796\n1979,Bini et al.,2.780\n1981,Schönhage,2.522\n1982,Coppersmith & Winograd,2.496\n2010,Stothers,2.3737\n2012,Williams,2.3729\n2024,\"Duan, Wu & Zhou\",2.371339\n2026,\"Dupont, et al.\",2.371177`,\n d3.autoType\n);","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined"},{"id":10,"value":"const getCurve = (exponent) => d3.range(0, 100).map(n => ({n, t: n ** exponent}));\nconst lineGen3d = d3.line().x(d => d[0]).y(d => d[1]);\nconst curves3d = data.map(d => {\n const Z = zFor(d.year);\n const pts = getCurve(d.exponent).map(({n, t}) => project3d(n, t, Z));\n return {\n ...d,\n Z,\n pts,\n linePath: lineGen3d(pts),\n start: pts[0],\n end: pts[pts.length - 1],\n base: project3d(99, 0, Z)\n };\n});","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined"},{"id":11,"value":"const allX3d = curves3d.flatMap(c => c.pts.map(p => p[0]));\nconst allY3d = curves3d.flatMap(c => c.pts.map(p => p[1]));\nconst [minX3d, maxX3d] = d3.extent(allX3d);\nconst [minY3d, maxY3d] = d3.extent(allY3d);","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined"},{"id":9,"value":"$33","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined"}],"files":"$W34","stdlib":"2","titling":"auto"}} 31:"$30:body"