Iterate over coefficients from a polynomial constructed from a string in JavaScript

Question

TL;DR: I need a way to create a polynomial from some given coordinates in a such a way to allow for iterating over its coefficients and optionally to even allow evaluating the polynomial at any given point

I am working on creating a crude algorithm in JavaScript/TypeScript for KZG commitments and one of the steps for this algorithm includes multiplying coefficients of the polynomial constructed for some given string with the Structured Reference String (SRS) raised to the appropriate power.

Anyway, that basically means I need to iterate over all of the coefficients of this newly constructed polynomial (at least that is what I think I need to do, I am open to suggestions here).

I am trying to achieve the following:

1. Take an input string
2. Convert the string into coordinates on the XY-coordinate plane
3. Calculate the polynomial that passes through these coordinates
4. **Iterate over coefficients of this polynomial **<-- this is where I am stuck
5. (optional) evaluate the polynomial at a given point Z <-- it would be awesome if this could still be possible alongside the previous requirement

I am stuck at step 4).

I know how to construct a polynomial from a given string in JS/TS using Lagrange Interpolation, but I am having difficulties extracting its coefficients, which I need to be able to multiply them with SRS.

Below is my Lagrange Interpolation algorithm - note that it can solve 5) for me, but I do not see an obvious way to get the exact coefficients from it:

type Point = { x: number; y: number };

// The function basically reconstructs the whole Lagrange Polynomial each time
// it needs to evaluate it at some given point `newX`, which is a problem as
// there is no way to extract the coefficients.
function lagrangeInterpolation(points: Point[], newX: number) {
  const n = points.length;
  let newY = 0;

  for (let i = 0; i < n; i++) {
    let { x, y } = points[i];

    let term = y;
    for (let j = 0; j < n; j++) {
      if (i !== j) {
        let { x: xj } = points[j];
        term = (term * (newX - xj)) / (x - xj);
      }
    }
    newY = newY + term;
  }

  return newY;
}

Maybe another interpolation algorithm would allow to calculate the exact coefficients?

I could not find any JS libraries that solve this exact problem. The closest ones I could find were the following, but they are still not applicable to solving this problem:

• polynomial -> problem: the library neither has an inbuilt way to return coefficients nor can it take a Lagrange-like polynomial as an input and shorten it to allow for coefficient extraction using regex.
• nerdamer-prime -> problem: the library can take any polynomial and shorten it, but it doesn't guarantee the order of terms (sorted by the power of x) which makes it difficult to extract coefficients using regex (cannot determine which coefficient is related to which power of x); it also has no inbuilt way to get coefficients.

Answer 1

You could use the matrix-based method described by @guest at Coefficients of Lagrange polynomials.

For that you'd need to have a function that calculates the determinant of a matrix. For this you could use the Gaussian elimination method.

Here is an implementation:

function determinant(mat) { // Gaussian elimination method
    const n = mat.length;
    let det = 1;
    for (let r = 0; r < n; r++) {
        let r2 = r;
        while (!mat[r2][r]) {
            r2++;
            if (r2 >= mat.length) return 0;
        }
        const row = mat[r2];
        if (r2 !== r) { // Swap rows
            mat[r2] = mat[r];
            mat[r] = row;
            det = -det;
        }
        let div = row[r];
        if (!div) return 0;
        det *= div;
        for (let c = r; c < n; c++) row[c] /= div;
        for (let r2 = r+1; r2 < n; r2++) {
            const row2 = mat[r2];
            const mul = row2[r];
            for (let c = r; c < n; c++) {
                row2[c] -= mul * row[c]; 
            }
        }
    }
    return det;
}

// Similar to https://math.stackexchange.com/a/3253643/341715
function lagrangeInterpolationCoefficients(points) {
    const lagrangeDet = (j) => determinant(points.map((_, i) => 
        points.map(([a, b]) => i == j ? b : a ** i)
    ));
    const denom = lagrangeDet(-1);
    return points.map((_, j) => lagrangeDet(j) / denom);
}

const coefficientsToFunction = (coefficients) =>
    x => coefficients.reduce((sum, coeff, i) => sum + coeff * x**i, 0);

// Simple (imperfect) rendering of the polynomial:
const coefficientsToString = (coefficients) =>
    coefficients.map((coeff, i) => `${coeff}x^${i}`)
                .reverse().join(" + ")
                .replace(/x\^0|\^1\b|\b0x\^\d+/g, "")
                .replaceAll("+ -", "- ");

// Demo
const points = [[0, -1], [1, 1], [3, 8], [4, 10]];
const coefficients = lagrangeInterpolationCoefficients(points);
console.log("f(x) =", coefficientsToString(coefficients));
const f = coefficientsToFunction(coefficients);

// Verify that the created function returns 
//    the correct results for the given points
for (const [x, y] of points) {
    console.log({x, y, "f(x)": f(x)});
}