Home / Docs / Specification / 29. Numerics
29.17 Dense values
Edition 0.5 (ADR 0120 rules 26 to 54, V4, IF2 to IF8). Everything in this section exists only in packages of edition 0.5; in editions 0.1 to 0.4, Array is only the variant Json.Array, Matrix, Tensor and Lu are ordinary names, and the prelude has none of the functions of rules 6 and 26.
What has landed. The front end, the checker, the verifier and the interpreter implement Array[T], Matrix[T] and Tensor[T] with element types F64 and I8 to U64, and Lu[T] with the factorizations and solves on F64 elements. The interpreter runs every float kernel by the blocked kernels of rule 32. Not yet implemented, and refused until their steps land: to_finite (the kinds Finite64 and Finite32 themselves are in the prelude, §18 rule 9); the element types F32, Complex[F64], Complex[F32] and the measured ones; and simd required. Native code implements this section: a dense value is a header over a store of raw canonical F64 elements, shared by its views and by the copies of a together block, or of words for every other element type (integer elements stay words until the raw cells of ADR 0107 land); every buffer is reserved within the memory budget before it is allocated; map, zip_map, update and fold apply their function through the uniform word, a boxed F64 per element, until the raw cells land; in native code the float kernels run through the target variant chosen at start (rule 56), and the interpreter runs the baseline. Both engines print the same text and the same bits.
-
Types.
Array[T],Matrix[T],Tensor[T]andLu[T]are built-in types.Array[T]takes any element type: it is the language's one fixed-length array.Matrix[T]andTensor[T]take a numeric element type,F64or one ofI8toU64, or a refinement or a measured version of one (Matrix[I32 in 0..1000],Matrix[F64 of Meter], spec/25 §9), andLu[T]takesF64; any other, a type parameter included, is U2002, at the type or at a call whose result would be one (matrix_filled(rows: 1, columns: 1, value: "a")). A kind, variant, capability or unit namedArray,Matrix,TensororLuis U1002, and no declaration hides the types.Matrix(...),Tensor(...)andLu(...)are U2001: the types have no constructor, and anLu[T]comes only fromlu()(rule 28). The prelude's variantJson.Arraykeeps its name: it is a constructor, written with parentheses, and the type is written with brackets, so the two never meet;Array(...)where anArray[T]is expected is U2001, with the repair toarray(...). -
Values. A dense value is a shape and its elements: an
Arrayhas a length, aMatrixrows and columns, and aTensora rank from 1 to 8 and a length along each axis, each length at least 0. Values are immutable.==compares the shapes, then each element by its type's==, in row-major order; a dense value satisfiesEqwhen its element type does, and neverOrd. The representation is not observable (spec/16 §4): numeric elements live in one buffer, row-major, and a float element there is canonical (§6). -
The numeric methods. The methods of rules 7 to 12 exist on numeric elements only, as each rule says; on another element type, the name resolves as a function of the package (spec/10 §5). The functions of the prelude that implement the methods are reached by their receiver only: no name in a program finds them.
-
Shapes and indexing. These are in the refinement language:
a.len,m.rows,m.columns,t.rankandt.dim(axis: k), each anIntof at least 0 and a rank from 1 to 8, anda.get(index: i),m.get(row: i, column: j)andt.get(at: [i, j])over integer elements. An element ofF64in a clause is U2014 until §8 lands. A tensor's methods are rule 26's.Method Result Contract a.get(index: i)Trequires 0 <= i and i < a.len;ensures result == a.get(index: i)m.get(row: i, column: j)Trequires 0 <= i and i < m.rows and 0 <= j and j < m.columnsa.at(index: i),m.at(row: i, column: j)Option[T]Noneexactly when an index is out of rangeedit a.set(index: i, item: x),edit m.set(row: i, column: j, item: x)Unitthe requiresofget;ensuresthe shape is unchanged andgetat that position isxgetandsetkeep their run-time bounds check in every build. Its failure can come only from a proven precondition that was false, a verifier bug: an internal abort (U8001), never a failure the program handles. Every dense method that takes its receiver byeditis writtenedit x.m(...), as a whole statement (U2020, U3013); a method that reads its receiver is not. -
Views. These are O(1), share the storage of the value they come from, and are values like any other. Bounds are half-open,
fromincluded anduntilexcluded:View Requires Ensures a.slice(from: i, until: j)0 <= i and i <= j and j <= a.lenresult.len == j - im.row(index: i)0 <= i and i < m.rowsresult.len == m.columnsm.column(index: j)0 <= j and j < m.columnsresult.len == m.rowsm.block(row_from: i, row_until: j, column_from: k, column_until: l)0 <= i and i <= j and j <= m.rows and 0 <= k and k <= l and l <= m.columnsresult.rows == j - i and result.columns == l - km.transpose()result.rows == m.columns and result.columns == m.rowsx.compact()copies a view into storage of its own, O(size), and ensures the same shape; until then, a view keeps its parent's whole storage alive.sliceandcompactexist on everyArray; the other views on numeric elements. -
Construction. The prelude gains these functions; a package declaration MAY reuse one of the names and wins over it (spec/10 §11 rule 5):
Function Result Contract array(xs: List[T])Array[T]ensures result.len == xs.lenarray_filled(length: n, value: x)Array[T]requires n >= 0;ensures result.len == nmatrix(rows: r, columns: c, elements: xs)Matrix[T]requires r >= 0 and c >= 0 and xs.len == r * c, row-major;ensures result.rows == r and result.columns == cmatrix_filled(rows: r, columns: c, value: x)Matrix[T]requires r >= 0 and c >= 0; the sameensuresmatrix_diagonal(values: a)Matrix[T]ensures result.rows == a.len and result.columns == a.len;aon the diagonal,+0of the element type elsewhereComputed elements keep no refinement. A function that computes new elements, rather than returning elements it was given, gives its result over the element type's base:
matrix_diagonalplaces+0off the diagonal, so overI32 in 1..10it gives aMatrix[I32], and so do every reduction and product of rules 9 and 10 and the element-wise operators of rule 7. A refinement of the element type flows through only where every element of the result is one of the arguments' (spec/03 §3, ADR 0103 rule 5). Such a function is not a function value: a value's result type is fixed where the value flows, after its type arguments take their refinements, so it would claim the refinement for elements the function made. Namingmatrix_diagonal, or any other function of this kind, as a value is U2001; a lambda that calls it is a function value. -
Element-wise operators (numeric elements).
x + yandx - ybetween two dense values of one type and one shape, and-x, apply the element type's operator to each element. Their precondition is the same shape: equal lengths, or equal rows and equal columns. Each is thezip_map(ormap) of rule 8 with the lambdafn(p, q) -> p + q; on a fixed-width element type it carries that lambda'soverflowobligation over two values of the element type, proven when the element type is a refinement that bounds it, and refuted otherwise. A program that means wrapping or saturating arithmetic writes it in azip_map.k * x,x * kandx / k, withka scalar of the element type, apply the operator to each element:x / kdivides, never multiplies by a reciprocal. On fixed-width elements they carry the sameoverflowobligation, andx / kthedivisionobligation once.- No
*and no/between two dense values: U2001, with the repairsx.multiply(by: y), the matrix product, andx.multiply_elements(by: y)(for/,x.divide_elements(by: y)). For two square matrices both are well shaped, so the shapes cannot tell which one a program means. - No implicit broadcasting: a dense value and a scalar under
+or-, a scalar divided by a dense value,mod, anArraywith aMatrix, and an operator on elements that are not numeric, are U2001. A broadcast is written withmap, which captures the scalar. x.multiply_elements(by: y)andx.divide_elements(by: y), onF64elements, of one shape.- The operators are not in the refinement language (U2014 in a clause).
-
Element-wise functions (numeric elements).
x.map(each: f)andx.zip_map(with: y, each: g)give a dense value of the shape ofx(zip_maprequires the same shape);edit x.update(each: f)replaces each element in place;x.fold(initial: v, step: g)visits the elements in row-major order, left to right. The function's type has nousesand nofails, and the function is called once per element, in row-major order.a.to_list()gives the elements of an array as aList[T], O(n). -
Reductions (
F64elements unless stated):Method Result Definition a.sum(),m.sum()F64rule 13 m.row_sums(),m.column_sums()Array[F64]each row's or column's sum by rule 13 a.dot(with: b)F64requires a.len == b.len; rule 14a.norm2()F64rule 15 x.all_finite()Boolevery element finite a.sum_exact(),m.sum_exact(),a.dot_exact(with: b)Intfixed-width elements; exact -
Product kernels (
F64elements):Method Contract Definition a.multiply(by: b)requires a.columns == b.rows;ensures result.rows == a.rows and result.columns == b.columnseach element by rule 14 from +0m.multiply_array(by: v)requires m.columns == v.len;ensures result.len == m.rowseach element by rule 14 from +0edit c.add_product(of: a, and: b)requires c.rows == a.rows and a.columns == b.rows and b.columns == c.columns; shape kepteach element by rule 14 from c's elementedit y.add_scaled(x, by: k)requires y.len == x.len; length kepty_i = fma(k, x_i, y_i)edit x.scale(by: k)shape kept x_i * kSo
u.dot(with: v), element (i, j) ofa.multiply(by: b)when row i ofaisuand column j ofbisv, and element i ofm.multiply_array(by: v)when row i ofmisu, are the same chain and the same bits. Each kernel checks the shape it ensures before it returns; a violation is an internal abort. The factorizations and solves are rule 28's. -
Updates. A method that takes its receiver by
editupdates the storage in place when the value and its storage are held once, and otherwise copies the receiver's own elements into fresh storage first, O(size of the receiver): an update of a view never changes its parent. No dense method fails. -
Rendering.
to_text, interpolation and the Una form write the construction call that rebuilds the value, elements in row-major order:array([1.0, 2.0]),matrix(rows: 2, columns: 2, elements: [1.0, 2.0, 3.0, 4.0]). JSON goes throughto_list()andarray(...), so spec/23 does not change.
Definitions by scalar chains. Each element of a dense result is computed by a chain of the operations of §3, with operands and an order that these rules fix. An implementation MAY block, vectorize, and run independent chains, or the independent blocks of rule 14, in any order or at once; it MUST NOT change a chain. So every engine, on every target, gives the bits of the plain loops of these rules. While edition 0.5 is a preview, the lane width L of rule 13 and the block size KB of rule 14 are unsettled points (ADR 0121 rule 5); every other part of the chains is settled.
- Lane-blocked sums. A sum of n
F64elements uses L = 32 lanes, 256 bytes of elements: every lane starts at+0; element k, in row-major order, is added to lanek mod 32, in increasing k (lane = lane + x_k); then the lanes combine in a fixed tree, for w = 16, 8, 4, 2, 1, lane l becominglane_l + lane_(l+w)for each l below w; the result is lane 0. So a sum of no elements, and a sum whose terms are all-0.0, is+0.0. The last digits of a sum can differ from a left-to-right loop; a program that needs that order writesfold. - Inner products, in blocks of KB = 64. For K terms with factors x_k and y_k: the terms are cut into consecutive blocks of 64, the last one shorter; each block is one chain from
+0,p = fma(x_k, y_k, p)in increasing k; the accumulator starts at+0(at the element ofcforadd_product), and each block's p is added to it in block order,s = s + p. With K = 0, the result is the accumulator's start. norm2, scaled. With M the largest|x_k|by totalOrder:+0.0when M is zero or there is no element; M when M is NaN or an infinity; otherwise, with e the integer such that2^(e-1) <= M < 2^e, each x_k is scaled toldexp(x_k, -e), the scaled values' sum of squares is the dot product of rule 14 of the scaled array with itself, and the result isldexp(sqrt(that sum), e).ldexp(y, k)isy × 2^kcorrectly rounded, ties to even, computed without forming2^k. Sonorm2overflows only when the norm itself exceeds the largest finite value, andarray([1.0e-200]).norm2()is1.0e-200.- No early exit.
==andall_finitecompare or scan every element, with a flag, and decide after;luandcholeskycompute to their end whatever the values, and decide after (rule 31).
Verification.
-
Sorts and functions. Each instantiated dense type is an uninterpreted sort,
i!Array_<T>,i!Matrix_<T>,i!Tensor_<T>andi!Lu_<T>, withi!len!,i!rows!,i!columns!,i!rank!andi!size!intoInt, andi!dim!from a tensor and anIntintoInt, each with the ground fact>= 0for every term that occurs, and1 <= rank <= 8for a rank. The element isi!get!<sort>from the value and oneIntper axis into the element's sort; a tensor has one such function per rank,i!get!<sort>!<r>with r indices, so that every application has a fixed arity. A tensor also has its element count,i!count!, which no program writes: for every count that occurs,rank = rimplies that the count is the product of the first r lengths, for r from 1 to 8, products that stay uninterpreted (spec/12 §2) and are model-checked as any other. The constructors of a tensor ensure its count as the product of their lengths, linear when the lengths are literals, andreshaperequires it, so a reshape of literal lengths verifies. Therequiresandensuresof the methods are those of the prelude, which is trusted and not verified (spec/12 §3); each kernel checks its shapeensureswhen it returns. The methods whose result is anOptionstate their shapes onSometo the verifier directly, since a clause cannot name the value anOptionholds:luanLu[T]of sizem.rows,solvea matrix ofm.rowsrows andrhs.columnscolumns,solve_arrayan array ofm.rows, andcholeskya matrix ofm's shape. Facts about the elements other than a written one would need a quantifier, so they are not stated, as forseton a list. -
The shape frame. The length frame of spec/17 §5 rule 3 extends to shapes: a dense binding that a loop updates keeps its shape when every completing path gives it a value whose callee ensures an unchanged shape, its length for an array, its rows and its columns for a matrix, and its rank, its element count and its length along each of the 8 axes for a tensor, as every
editmethod of this section does. The verifier then assumes the starting shape in the body and after the loop, so this loop proves everygetandsetin bounds:unafor i in 0..<m.rows for j in 0..<m.columns let x = m.get(row: i, column: j) edit m.set(row: i, column: j, item: x * 2.0)The read comes first, as its own
let: a call that passesmbyeditcannot readmin its other arguments (U2018, spec/17 §3).The same loop over
0..m.rows, which reachesi == m.rows, is refuted atget, U5001, with the counterexamplei == m.rows. -
What verifies: the shape preconditions of a whole computation, products included; indices in loops over the shape; views and their shapes; same shape over tensors of every rank, which expands to the rank and, for each axis k from 0 to 7,
k < rankimplying equal lengths along k, at most 17 linear atoms; reshapes whose lengths are literals; a solve with the factorization oflu(). What does not: values of sums and products, facts over all the elements, which a program states at a checked boundary or tests withall_finite(), and reshapes whose lengths are products of values, which spec/12 §6 reports as unknown unless the interpreted re-solve of ADR 0054 refutes them.
Information flow.
- Positions. A dense type has a top position, which covers its shape and its existence, and an element position:
Matrix[secret F64]haspublicshapes andsecretelements, asList[secret F64]has. Flows are covariant. - Reads.
len,rows,columns,rank,dimandsizetake the top label.getandattake the element label joined with the top label and every label of the indices; the top ofat'sOptiontakes the top label and the indices' labels. A view's top takes its value's top and the labels of its bounds or index. - Writes. The item of
setflows into the element position, joined with the program counter. Where a value lands reveals its index, so an index abovepublicis U4001: in this step the index ofsetis apublicargument, which is stricter than ADR 0120 IF4 (a labeled index into elements of at least its label); a later step may admit that case. - Element-wise operations,
map,zip_mapandupdate: each result element carries the labels of the operand elements and of the scalars and captured values, and the top the operands' tops. - Reductions and kernels. A sum, a product, a norm,
all_finite, a contraction, a factorization and a solve depend on many elements, and a factorization and a solve on the pivots chosen from their values: a scalar result, and every position of a dense result, carries the labels of every element and top of every input. So the top of theOptionthatlu,cholesky,solveandsolve_arrayreturn carries them too, sinceNoneis decided by values, and every position of anLu[T], whosesize,factors()andpivots()carry the labels of the matrix it came from. The kernels that update their receiver from other dense values (add_product,add_scaled) flow the inputs' top labels into the receiver's element position too (U4001 above it). - What stays out of model: timing, as spec/07 §1 states, and termination by the memory budget: whether a buffer is refused (U6003) is decided by a shape, so a run that builds a dense value of a
secretshape may stop or not depending on it, the resource channel of a list ofsecretlength. Theout_of_modelentriestiming,termination and divergence, andresource consumption and allocation(spec/13 §6) cover them.
Tensors.
-
Tensor methods. A tensor's shape, index and permutation are list literals of 1 to 8 elements, and an axis is an integer literal from 0 to 7, so each call takes the contract of its rank, stated over the literal's elements; any other form is U2038, and so is
tensorortensor_fillednamed as a function value. The elements of a shape or an index list are anyIntexpressions; those of a permutation are integer literals.Method Requires Ensures tensor(shape: [d0, ..., dk], elements: xs)each dq >= 0;xs.lentheir productresult.rank == k + 1,result.dim(axis: q) == dq; row-majortensor_filled(shape: [d0, ..., dk], value: x)each dq >= 0the same t.get(at: [i0, ..., ik]),edit t.set(at: [...], item: x)t.rank == k + 1and each index in rangeget's element;setkeeps the shape and givesgettherext.at(at: [...])Noneexactly when the literal has another length than the rank, or an index is out of ranget.dim(axis: k)k < t.rankt.dim(axis: k)t.permute(axes: [p0, ..., pk])t.rank == k + 1result.rank == k + 1,result.dim(axis: q) == t.dim(axis: pq); a view, O(rank)t.reshape(shape: [d0, ..., dk])each dq >= 0, their product the element countresult.rank == k + 1,result.dim(axis: q) == dq; a view of a contiguous tensor, otherwise a compacting copy, O(n)t.sum()the sum of every element, by rule 13 ( F64elements)t.sum(axis: k)2 <= t.rankandk < t.ranka tensor of rank t.rank - 1, the remaining axes in order, each element a sum of rule 13 along axis kt.contract(with: u, axis: k, other: l)k < t.rank,l < u.rank,t.dim(axis: k) == u.dim(axis: l),3 <= t.rank + u.rank <= 10the remaining axes of t, then ofu; each element an inner product of rule 14, so a contraction of two rank-2 tensors has the bits ofmultiplya.to_tensor(),m.to_tensor(),t.to_array(),t.to_matrix()rank 1 or 2 for the last two the shape, axis by axis; views, O(1) compact,map,zip_map,update,fold,multiply_elements,divide_elements,all_finite,sum_exactand the operators of rule 7 are a tensor's as an array's and a matrix's are, of one shape.sum(axis:)gives aTensor[T]also when the result's rank is 1, whichto_array()converts.contractof two tensors of rank 1, whose result would have no axis, is excluded by its precondition: theirdotis that ofto_array(). -
Rendering. A tensor renders as
tensor(shape: [2, 1], elements: [1.0, 2.0]), its elements in row-major order.
Factorizations.
-
Lu[T]and the solves (F64elements):Method Requires Result a.lu()a.rows == a.columnsOption[Lu[T]]: onSome(f),f.size == a.rows;Nonewhen a pivot is exactly zerof.solve(rhs: b)b.rows == f.sizea matrix of f.sizerows andb.columnscolumnsa.solve(rhs: b)a.rows == a.columnsandb.rows == a.rowsOption[Matrix[T]], ofb's shape onSome:a.lu(), then itssolvea.solve_array(rhs: v)a.rows == a.columnsandv.len == a.rowsOption[Array[T]]ofv.lenonSome; the same with one columna.cholesky()a.rows == a.columnsOption[Matrix[T]]: the lower factor, ofa's shape,+0above the diagonal;Nonewhen not positive definitel.solve_lower(rhs: b, unit_diagonal: u),r.solve_upper(rhs: b, unit_diagonal: u)square, and b.rowsits sizea matrix of b's shape; withunit_diagonal: truethe diagonal is taken as 1 and not readLu[T]is opaque. It has no constructor (U2001), so no program forges one, and no operator applies to it (U2001). Its accessors aref.size, anIntin the refinement language with the factf.size >= 0,f.factors(), aMatrix[T]view off.size×f.sizeholding L below the diagonal, its unit diagonal implied, and U on and above it, andf.pivots(), theList[Int]of the rows exchanged at each step, O(n). It satisfiesEq, by its factors and its pivots, and renders as<lu size 3>, which is not source.What a result holds. LU with partial pivoting is backward stable in practice, with a worst-case growth factor of 2^(n-1) for contrived matrices.
Nonefromlu()means an exactly zero pivot; a nearly singular matrix givesSome, with large or non-finite elements, and there is no condition estimate.cholesky()reads the lower triangle only, so a matrix that is not symmetric is factored as the symmetric matrix of its lower triangle. The diagonal off.factors()is U's: to solve with L, writesolve_lower(rhs: b, unit_diagonal: true). -
LU, blocked by KB = 64. In panels of 64 columns, the last one narrower; for each panel
[b, e): (1) for each column k of the panel in increasing order, the pivot is the smallest rowp >= kwhose|a_pk|is greatest by totalOrder, so a NaN is chosen first, and an exactly zero pivot marks the matrix singular while the factorization runs on; rows p and k are exchanged across all columns;l_ik = a_ik / a_kk, a true division, for eachi > k; anda_ij = fma(-l_ik, a_kj, a_ij)for eachi > kand each panel columnj > k; (2) for each k of the panel in increasing order, each panel rowi > kand each columnj >= e,a_ij = fma(-l_ik, a_kj, a_ij); (3) for eachi, j >= e, one block of rule 14 from+0over the panel's k with-l_ikanda_kj, added toa_ij.f.solve(rhs: b)applies the exchanges in order, then the lower solve of rule 31 with a unit diagonal, then the upper one. -
Cholesky, blocked by KB = 64. On the lower triangle, in panels of 64 columns; for each panel
[b, e)and each column j of it in increasing order:s = a_jj, thens = fma(-l_jk, l_jk, s)for each panelk < jin increasing order; ansthat is not greater than zero by the IEEE comparison marks the matrix not positive definite while the factorization runs on;l_jj = sqrt(s); and for eachi > j,t = a_ij, thent = fma(-l_ik, l_jk, t)for the same k, andl_ij = t / l_jj. Then for eachi >= j >= e, one block of rule 14 from+0over the panel's k with-l_ikandl_jk, added toa_ij. -
Triangular solves, blocked by KB = 64. For each column of the right-hand side, the rows are taken in order, increasing for
solve_lowerand decreasing forsolve_upper, and that sequence is cut into blocks of 64, the last one shorter. Within a block, for each of its rows i in order,t = b_i, thent = fma(-t_ik, x_k, t)for each earlier row k of the block in the block's order, andx_i = t / t_ii, orx_i = twithunit_diagonal: true. Once a block is solved, each later row i gets one block of rule 14 from+0over the block's rows k in the block's order, with-t_ikandx_k, added tob_i. A zero on the diagonal gives infinities or NaN, never a failure.luandcholeskyrun to their end whatever the values (rule 16): their running time does not reveal where a zero pivot is. -
The kernels and their corpus. Each chain of rules 10, 13 to 15 and 29 to 31 has, in
una-core, which both engines share, a reference that writes it as plain loops, and a blocked kernel for each target's baseline, which the interpreter runs (ADR 0120 rule 53). A blocked kernel changes only the order in which independent chains run, and keeps the partial sums of up to 64 outputs in a tile: a product runs by tiles of 64 columns, then blocks of 64 terms, then rows; LU and Cholesky are the right-looking algorithms of rules 29 and 30, their trailing updates by tiles of 64 columns; a triangular solve runs every column of its right-hand side at once. Itsfmais IEEEfusedMultiplyAdd: the instruction where the target's baseline has one (AArch64), and otherwise an exact emulation by error-free transformations, Dekker's product and Knuth's sum, then an addition rounded to odd and a final rounding to nearest (Boldo and Melquiond, 2008); for operands or partial results outside the range where that emulation is proven exact (an operand that is subnormal or of magnitude2^995or more, factors whose exponents sum below -960 or above 1020, an addend of2^1021or more, or a rounded third step whose leading sum is below2^-968), the emulation computes the result by the routine of §6 rule 5 instead, with the same bits. Every float a kernel stores is canonical (§6 rule 1), and no kernel returns early on a value (rule 16). A corpus of inputs and of the bits of their outputs is part of the implementation: shapes empty, of one element, around 32 and 64 and their multiples, of two and three panels, singular and not positive definite in a chosen panel, and values NaN, infinite, zero of both signs, subnormal, extreme and random; andfmaoperands near overflow, near the underflow threshold and subnormal, cancellations and halfway cases. Its expected bits come from an implementation of the chains independent of the compiler's, with exact rationalfmaandldexp, and every reference and every blocked kernel reproduces them bit for bit. -
Units. The element type carries the unit, one for every element (ADR 0120 rule 64): the element-wise operators follow the scalar rules, a scalar's unit multiplies or divides the elements',
multiply_elements,dot,multiplyandmultiply_arraymultiply the units, andmagnitude()andmeasured()are O(1) (spec/25 §9).
Cost. get, set, at and the shape terms are O(1); the views of rule 5 are O(1); compact, a copy on write and to_list are O(n); element-wise operations, map, zip_map, update, fold, the sums, dot, norm2, all_finite and == are O(n); multiply_array is O(mn) and multiply, add_product and contract O(mkn), by the chains of rule 14; Strassen-type products are not used. permute, the conversions of rule 26 and a reshape of a contiguous tensor are O(1) or O(rank); a reshape of another tensor is O(n). lu is O(2n³/3) and cholesky O(n³/3), also when they find no factorization; a solve with r right-hand sides is O(n²r), and solve_lower and solve_upper are O(n²r). Every buffer, and every workspace of a factorization or a solve, is checked against the memory budget before it is allocated, in checked arithmetic, and a refused one is U6003. Every kernel of rule 32 runs in O(1) space beyond its result, or beyond the matrix it factors or the right-hand side it solves in place; an operand that is a view of another layout than row-major (a column, a transpose) is first copied, O(size), within the budget. On x86-64 the interpreter's kernels compute every fma by the emulation of rule 32, so they are slower than native code's, with the same bits; on AArch64 they use the instruction.