Home / Docs / Specification / 29. Numerics

29.17 Dense values

Release v0.4.0

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.

  1. Types. Array[T], Matrix[T], Tensor[T] and Lu[T] are built-in types. Array[T] takes any element type: it is the language's one fixed-length array. Matrix[T] and Tensor[T] take a numeric element type, F64 or one of I8 to U64, or a refinement or a measured version of one (Matrix[I32 in 0..1000], Matrix[F64 of Meter], spec/25 §9), and Lu[T] takes F64; 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 named Array, Matrix, Tensor or Lu is U1002, and no declaration hides the types. Matrix(...), Tensor(...) and Lu(...) are U2001: the types have no constructor, and an Lu[T] comes only from lu() (rule 28). The prelude's variant Json.Array keeps its name: it is a constructor, written with parentheses, and the type is written with brackets, so the two never meet; Array(...) where an Array[T] is expected is U2001, with the repair to array(...).

  2. Values. A dense value is a shape and its elements: an Array has a length, a Matrix rows and columns, and a Tensor a 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 satisfies Eq when its element type does, and never Ord. The representation is not observable (spec/16 §4): numeric elements live in one buffer, row-major, and a float element there is canonical (§6).

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

  4. Shapes and indexing. These are in the refinement language: a.len, m.rows, m.columns, t.rank and t.dim(axis: k), each an Int of at least 0 and a rank from 1 to 8, and a.get(index: i), m.get(row: i, column: j) and t.get(at: [i, j]) over integer elements. An element of F64 in a clause is U2014 until §8 lands. A tensor's methods are rule 26's.

    Method Result Contract
    a.get(index: i) T requires 0 <= i and i < a.len; ensures result == a.get(index: i)
    m.get(row: i, column: j) T requires 0 <= i and i < m.rows and 0 <= j and j < m.columns
    a.at(index: i), m.at(row: i, column: j) Option[T] None exactly when an index is out of range
    edit a.set(index: i, item: x), edit m.set(row: i, column: j, item: x) Unit the requires of get; ensures the shape is unchanged and get at that position is x

    get and set keep 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 by edit is written edit x.m(...), as a whole statement (U2020, U3013); a method that reads its receiver is not.

  5. Views. These are O(1), share the storage of the value they come from, and are values like any other. Bounds are half-open, from included and until excluded:

    View Requires Ensures
    a.slice(from: i, until: j) 0 <= i and i <= j and j <= a.len result.len == j - i
    m.row(index: i) 0 <= i and i < m.rows result.len == m.columns
    m.column(index: j) 0 <= j and j < m.columns result.len == m.rows
    m.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.columns result.rows == j - i and result.columns == l - k
    m.transpose() result.rows == m.columns and result.columns == m.rows

    x.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. slice and compact exist on every Array; the other views on numeric elements.

  6. 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.len
    array_filled(length: n, value: x) Array[T] requires n >= 0; ensures result.len == n
    matrix(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 == c
    matrix_filled(rows: r, columns: c, value: x) Matrix[T] requires r >= 0 and c >= 0; the same ensures
    matrix_diagonal(values: a) Matrix[T] ensures result.rows == a.len and result.columns == a.len; a on the diagonal, +0 of the element type elsewhere

    Computed 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_diagonal places +0 off the diagonal, so over I32 in 1..10 it gives a Matrix[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. Naming matrix_diagonal, or any other function of this kind, as a value is U2001; a lambda that calls it is a function value.

  7. Element-wise operators (numeric elements).

    • x + y and x - y between 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 the zip_map (or map) of rule 8 with the lambda fn(p, q) -> p + q; on a fixed-width element type it carries that lambda's overflow obligation 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 a zip_map.
    • k * x, x * k and x / k, with k a scalar of the element type, apply the operator to each element: x / k divides, never multiplies by a reciprocal. On fixed-width elements they carry the same overflow obligation, and x / k the division obligation once.
    • No * and no / between two dense values: U2001, with the repairs x.multiply(by: y), the matrix product, and x.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, an Array with a Matrix, and an operator on elements that are not numeric, are U2001. A broadcast is written with map, which captures the scalar.
    • x.multiply_elements(by: y) and x.divide_elements(by: y), on F64 elements, of one shape.
    • The operators are not in the refinement language (U2014 in a clause).
  8. Element-wise functions (numeric elements). x.map(each: f) and x.zip_map(with: y, each: g) give a dense value of the shape of x (zip_map requires 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 no uses and no fails, and the function is called once per element, in row-major order. a.to_list() gives the elements of an array as a List[T], O(n).

  9. Reductions (F64 elements unless stated):

    Method Result Definition
    a.sum(), m.sum() F64 rule 13
    m.row_sums(), m.column_sums() Array[F64] each row's or column's sum by rule 13
    a.dot(with: b) F64 requires a.len == b.len; rule 14
    a.norm2() F64 rule 15
    x.all_finite() Bool every element finite
    a.sum_exact(), m.sum_exact(), a.dot_exact(with: b) Int fixed-width elements; exact
  10. Product kernels (F64 elements):

    Method Contract Definition
    a.multiply(by: b) requires a.columns == b.rows; ensures result.rows == a.rows and result.columns == b.columns each element by rule 14 from +0
    m.multiply_array(by: v) requires m.columns == v.len; ensures result.len == m.rows each element by rule 14 from +0
    edit c.add_product(of: a, and: b) requires c.rows == a.rows and a.columns == b.rows and b.columns == c.columns; shape kept each element by rule 14 from c's element
    edit y.add_scaled(x, by: k) requires y.len == x.len; length kept y_i = fma(k, x_i, y_i)
    edit x.scale(by: k) shape kept x_i * k

    So u.dot(with: v), element (i, j) of a.multiply(by: b) when row i of a is u and column j of b is v, and element i of m.multiply_array(by: v) when row i of m is u, 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.

  11. Updates. A method that takes its receiver by edit updates 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.

  12. 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 through to_list() and array(...), 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.

  1. Lane-blocked sums. A sum of n F64 elements uses L = 32 lanes, 256 bytes of elements: every lane starts at +0; element k, in row-major order, is added to lane k 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 becoming lane_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 writes fold.
  2. 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 of c for add_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.
  3. norm2, scaled. With M the largest |x_k| by totalOrder: +0.0 when M is zero or there is no element; M when M is NaN or an infinity; otherwise, with e the integer such that 2^(e-1) <= M < 2^e, each x_k is scaled to ldexp(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 is ldexp(sqrt(that sum), e). ldexp(y, k) is y × 2^k correctly rounded, ties to even, computed without forming 2^k. So norm2 overflows only when the norm itself exceeds the largest finite value, and array([1.0e-200]).norm2() is 1.0e-200.
  4. No early exit. == and all_finite compare or scan every element, with a flag, and decide after; lu and cholesky compute to their end whatever the values, and decide after (rule 31).

Verification.

  1. Sorts and functions. Each instantiated dense type is an uninterpreted sort, i!Array_<T>, i!Matrix_<T>, i!Tensor_<T> and i!Lu_<T>, with i!len!, i!rows!, i!columns!, i!rank! and i!size! into Int, and i!dim! from a tensor and an Int into Int, each with the ground fact >= 0 for every term that occurs, and 1 <= rank <= 8 for a rank. The element is i!get!<sort> from the value and one Int per 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 = r implies 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, and reshape requires it, so a reshape of literal lengths verifies. The requires and ensures of the methods are those of the prelude, which is trusted and not verified (spec/12 §3); each kernel checks its shape ensures when it returns. The methods whose result is an Option state their shapes on Some to the verifier directly, since a clause cannot name the value an Option holds: lu an Lu[T] of size m.rows, solve a matrix of m.rows rows and rhs.columns columns, solve_array an array of m.rows, and cholesky a matrix of m's shape. Facts about the elements other than a written one would need a quantifier, so they are not stated, as for set on a list.

  2. 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 edit method of this section does. The verifier then assumes the starting shape in the body and after the loop, so this loop proves every get and set in bounds:

    una
    for 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 passes m by edit cannot read m in its other arguments (U2018, spec/17 §3).

    The same loop over 0..m.rows, which reaches i == m.rows, is refuted at get, U5001, with the counterexample i == m.rows.

  3. 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 < rank implying equal lengths along k, at most 17 linear atoms; reshapes whose lengths are literals; a solve with the factorization of lu(). What does not: values of sums and products, facts over all the elements, which a program states at a checked boundary or tests with all_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.

  1. Positions. A dense type has a top position, which covers its shape and its existence, and an element position: Matrix[secret F64] has public shapes and secret elements, as List[secret F64] has. Flows are covariant.
  2. Reads. len, rows, columns, rank, dim and size take the top label. get and at take the element label joined with the top label and every label of the indices; the top of at's Option takes the top label and the indices' labels. A view's top takes its value's top and the labels of its bounds or index.
  3. Writes. The item of set flows into the element position, joined with the program counter. Where a value lands reveals its index, so an index above public is U4001: in this step the index of set is a public argument, which is stricter than ADR 0120 IF4 (a labeled index into elements of at least its label); a later step may admit that case.
  4. Element-wise operations, map, zip_map and update: each result element carries the labels of the operand elements and of the scalars and captured values, and the top the operands' tops.
  5. 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 the Option that lu, cholesky, solve and solve_array return carries them too, since None is decided by values, and every position of an Lu[T], whose size, factors() and pivots() 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).
  6. 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 secret shape may stop or not depending on it, the resource channel of a list of secret length. The out_of_model entries timing, termination and divergence, and resource consumption and allocation (spec/13 §6) cover them.

Tensors.

  1. 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 tensor or tensor_filled named as a function value. The elements of a shape or an index list are any Int expressions; those of a permutation are integer literals.

    Method Requires Ensures
    tensor(shape: [d0, ..., dk], elements: xs) each dq >= 0; xs.len their product result.rank == k + 1, result.dim(axis: q) == dq; row-major
    tensor_filled(shape: [d0, ..., dk], value: x) each dq >= 0 the same
    t.get(at: [i0, ..., ik]), edit t.set(at: [...], item: x) t.rank == k + 1 and each index in range get's element; set keeps the shape and gives get there x
    t.at(at: [...]) None exactly when the literal has another length than the rank, or an index is out of range
    t.dim(axis: k) k < t.rank t.dim(axis: k)
    t.permute(axes: [p0, ..., pk]) t.rank == k + 1 result.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 count result.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 (F64 elements)
    t.sum(axis: k) 2 <= t.rank and k < t.rank a tensor of rank t.rank - 1, the remaining axes in order, each element a sum of rule 13 along axis k
    t.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 <= 10 the remaining axes of t, then of u; each element an inner product of rule 14, so a contraction of two rank-2 tensors has the bits of multiply
    a.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_exact and the operators of rule 7 are a tensor's as an array's and a matrix's are, of one shape. sum(axis:) gives a Tensor[T] also when the result's rank is 1, which to_array() converts. contract of two tensors of rank 1, whose result would have no axis, is excluded by its precondition: their dot is that of to_array().

  2. Rendering. A tensor renders as tensor(shape: [2, 1], elements: [1.0, 2.0]), its elements in row-major order.

Factorizations.

  1. Lu[T] and the solves (F64 elements):

    Method Requires Result
    a.lu() a.rows == a.columns Option[Lu[T]]: on Some(f), f.size == a.rows; None when a pivot is exactly zero
    f.solve(rhs: b) b.rows == f.size a matrix of f.size rows and b.columns columns
    a.solve(rhs: b) a.rows == a.columns and b.rows == a.rows Option[Matrix[T]], of b's shape on Some: a.lu(), then its solve
    a.solve_array(rhs: v) a.rows == a.columns and v.len == a.rows Option[Array[T]] of v.len on Some; the same with one column
    a.cholesky() a.rows == a.columns Option[Matrix[T]]: the lower factor, of a's shape, +0 above the diagonal; None when not positive definite
    l.solve_lower(rhs: b, unit_diagonal: u), r.solve_upper(rhs: b, unit_diagonal: u) square, and b.rows its size a matrix of b's shape; with unit_diagonal: true the diagonal is taken as 1 and not read

    Lu[T] is opaque. It has no constructor (U2001), so no program forges one, and no operator applies to it (U2001). Its accessors are f.size, an Int in the refinement language with the fact f.size >= 0, f.factors(), a Matrix[T] view of f.size × f.size holding L below the diagonal, its unit diagonal implied, and U on and above it, and f.pivots(), the List[Int] of the rows exchanged at each step, O(n). It satisfies Eq, 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. None from lu() means an exactly zero pivot; a nearly singular matrix gives Some, 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 of f.factors() is U's: to solve with L, write solve_lower(rhs: b, unit_diagonal: true).

  2. 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 row p >= k whose |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 each i > k; and a_ij = fma(-l_ik, a_kj, a_ij) for each i > k and each panel column j > k; (2) for each k of the panel in increasing order, each panel row i > k and each column j >= e, a_ij = fma(-l_ik, a_kj, a_ij); (3) for each i, j >= e, one block of rule 14 from +0 over the panel's k with -l_ik and a_kj, added to a_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.

  3. 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, then s = fma(-l_jk, l_jk, s) for each panel k < j in increasing order; an s that 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 each i > j, t = a_ij, then t = fma(-l_ik, l_jk, t) for the same k, and l_ij = t / l_jj. Then for each i >= j >= e, one block of rule 14 from +0 over the panel's k with -l_ik and l_jk, added to a_ij.

  4. Triangular solves, blocked by KB = 64. For each column of the right-hand side, the rows are taken in order, increasing for solve_lower and decreasing for solve_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, then t = fma(-t_ik, x_k, t) for each earlier row k of the block in the block's order, and x_i = t / t_ii, or x_i = t with unit_diagonal: true. Once a block is solved, each later row i gets one block of rule 14 from +0 over the block's rows k in the block's order, with -t_ik and x_k, added to b_i. A zero on the diagonal gives infinities or NaN, never a failure. lu and cholesky run to their end whatever the values (rule 16): their running time does not reveal where a zero pivot is.

  5. 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. Its fma is IEEE fusedMultiplyAdd: 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 magnitude 2^995 or more, factors whose exponents sum below -960 or above 1020, an addend of 2^1021 or more, or a rounded third step whose leading sum is below 2^-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; and fma operands 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 rational fma and ldexp, and every reference and every blocked kernel reproduces them bit for bit.

  6. 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, multiply and multiply_array multiply the units, and magnitude() and measured() 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.