MATHEMATICS
Solving linear systems with a vector-sized workspace
A 2025 result published at SODA 2026 separates linear solves from quadratic working memory. Its scope depends on integer inputs, access models, and bit complexity.
Research checked
Newest cited publication
A matrix illustration provides context for solving linear systems while limiting the additional memory used by the algorithm.
Maschen / Wikimedia Commons. Wikimedia-generated PNG rendering of the SVG; no editorial changes. · Image source · Public domain (released by the creator)
A matrix may occupy an enormous amount of storage while a useful answer is just one vector. Does finding that vector necessarily require another matrix sized block of working memory? Yiping Liu, Hoai-An Nguyen, and Junzhao Yang investigate this question in Numerical Linear Algebra in Linear Space, first posted on July 3, 2025, and published in the proceedings of SODA 2026. Their result concerns a precise theoretical model of integer input systems and rational answers. It shows why memory complexity deserves to be studied separately from arithmetic speed, while also illustrating how easily a phrase such as linear space can become misleading when the model and accuracy requirement are left unstated.
Workspace is a specific resource
Suppose a matrix is supplied through read only access, and an algorithm writes its answer to an output stream. The memory needed to hold the input is different from the scratch memory used during the calculation. A theorem about workspace can exclude the input and output while counting every temporary value. This distinction is sensible when data already exist on disk or can be regenerated, but it does not make the original data free to store, read, or communicate.
For a simple scale comparison, an n by n dense array contains n² values. Ten additional vectors contain 10n values. When n is ten thousand, the counts are one hundred million versus one hundred thousand. That comparison says nothing about the number of times the algorithm must reread the input. An approach can save scratch memory by revisiting data or recomputing intermediate information. Its time cost and access pattern must therefore accompany the space bound before one can judge its practical appeal.
The reported guarantee and its boundaries
The paper gives a randomized solver for nonsingular integer systems Ax = b with rational solutions, with high probability of success. Its theorem allows an accuracy parameter ε between zero and one. With matrix entries bounded by U and right hand side entries bounded by U raised to n, it uses O(n log(nU)) bits of workspace and about n² log(1/ε) times the number of nonzero matrix entries in bit operations, suppressing additional logarithmic factors. For polynomially bounded U and fixed or inverse-polynomial accuracy, this yields the compact linear-workspace summary. It returns an entrywise multiplicative approximation without assuming a favorable condition number. SODA 2026 published the result first posted in 2025.
Every qualifier carries information. Bits are not interchangeable with floating point operations. Polynomially bounded integer entries constrain the input representation. Randomization requires a success guarantee rather than certainty for every random choice. Nonsingularity makes the solution unique. Entrywise accuracy is stronger in some respects than a single vector norm error. Finally, a small workspace does not imply that the solver outruns optimized numerical libraries. The theorem establishes a time and memory possibility under its model, rather than announcing a drop in replacement for a production sparse solver.
Remainders offer a different arithmetic viewpoint
Integer systems invite modular arithmetic. Instead of representing a large rational number immediately, calculations can be performed with remainders modulo a prime. For A with rows (2, 1) and (1, 3), and b = (1, 2), the rational solution is (1/5, 3/5). Modulo seven, five has multiplicative inverse three, so the corresponding solution is (3, 2). Substitution gives eight and nine, whose remainders are one and two, exactly the desired right hand side.
Modulo five, however, the same matrix has determinant zero and cannot be inverted. This small example explains why choosing a modulus requires care. It also shows why a modular answer is not an ordinary decimal approximation: three modulo seven represents a residue class, not a claim that one fifth is numerically close to three. Earlier exact linear system research, including the deterministic reduction by Stavros Birmpilis, George Labahn, and Arne Storjohann, develops reconstruction methods using arithmetic representations suited to integer structure. Such work supplies important background to the memory question.
A remainder alone cannot identify a rational number
Both one fifth and two thirds reduce to three modulo seven. The first does so because five times three has remainder one; the second because the inverse of three is five and two times five has remainder three. Modulo eleven they separate: one fifth becomes nine, while two thirds becomes eight. Combining information from different moduli can narrow the possibilities, but reconstruction still needs bounds that make the intended numerator and denominator identifiable.
This is an information constraint rather than a matter of clever implementation. Without bounds, infinitely many integers share any one remainder, and infinitely many rational descriptions can be compatible with finite modular observations. A correct exact arithmetic algorithm must budget enough information and enough memory to distinguish the admissible possibilities. The 2019 deterministic work addresses a different optimization target from the 2025 linear workspace result. Reading them together clarifies that fast reconstruction, low scratch storage, and low input access cost are separate properties to establish.
Why entrywise accuracy is a substantial demand
Consider a target vector (1, 0.000000000001). Replacing it by (1, 0) makes an extremely small relative error when measured in the ordinary Euclidean norm of the whole vector. Yet the second component has lost all of its value. A requirement that controls each nonzero entry multiplicatively rules out this failure. It also treats zero specially: no finite multiplicative factor turns a nonzero approximation into an exact zero target. This makes support recovery part of the strength of the stated guarantee.
The example is deliberately independent of any application. In some problems, a very small coordinate represents an important rare signal; in others, it is below the uncertainty of the input and has no defensible scientific meaning. The mathematical guarantee and the scientific usefulness are separate judgments. An algorithm can promise a strong relationship to the exact encoded input while the measurement process that produced those entries remains uncertain. Exact input mathematics does not automatically supply exact knowledge of the world.
Streaming imposes a different restriction
A method that may revisit input entries has more freedom than a method that sees each update once. In the turnstile streaming model, entries can receive additions or subtractions in arbitrary order, and the algorithm maintains a compact summary. Kenneth Clarkson and David Woodruff study this setting for matrix products, regression, rank, and low rank approximation. Their work provides both upper and lower space bounds for specified error requirements. It demonstrates why an access model belongs inside a theorem statement.
There is no contradiction when one model permits a small workspace and another proves that a small one pass summary is impossible for a related task. Repeated access can recover information that a stream must either retain immediately or lose. Even outside theory, this distinction changes system design. A matrix generated by a deterministic formula may be cheap to revisit. Measurements arriving from an instrument may be expensive or impossible to replay. A numerical method should therefore be selected with the actual data source in mind.
Removing a condition assumption does not remove sensitivity
For an elementary illustration, take a matrix with rows (N, N) and (N, N + 1), where N is large. The right hand side (2N, 2N + 1) has solution (1, 1). Increase only its second entry by one and the solution becomes (0, 2). The relative input change can be small when N is large while the answer changes substantially. An exact algorithm can distinguish the encoded inputs; it cannot decide whether a measured difference of one was physically trustworthy.
The linear workspace result is valuable precisely because it identifies a computational possibility without concealing its model. Future practical comparisons would need implementation costs, repeated access counts, bit widths, and behavior on realistic structured inputs. As of October 18, 2026, its recent SODA publication broadens the discussion of numerical linear algebra beyond raw speed. A vector answer need not force matrix sized scratch storage, but obtaining that economy requires careful choices about arithmetic, accuracy, and which information can be revisited.
Sources & further reading
Primary papers, project documentation, and research releases used in this article. Publication dates below refer to the sources themselves.
- Numerical Linear Algebra in Linear SpacearXivPublished Checked
- Numerical Linear Algebra in Linear SpaceProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete AlgorithmsChecked
- Numerical Linear Algebra in the Streaming ModelClarkson and Woodruff author manuscriptPublished Checked
- Deterministic Reduction of Integer Nonsingular Linear System Solving to Matrix MultiplicationUniversity of Waterloo author manuscriptChecked
FOLLOW THE QUESTION
Explore mathematics