3
\$\begingroup\$

I wrote this function and I'm interested if it can be sped up by improving the code. The function accepts either column major 1D array or 2D row major array. Maybe there are some obvious JS tricks that work faster?

const invert = (m, s, CM = false) => {

  const zrow = new Array(s).fill(0);

  const failCheck = (ind, piv) => {
    if (Math.abs(piv) < 1e-8) {
      console.error(`matrix ${m} is not invertible, pivot at step ${ind}: ${piv}`);
      return 1;
    }
    return 0;
  };

  const I = new Array(s);
  for(let k = 0; k < s; k++) {
    I[k] = [...zrow];
    I[k][k] = 1;
  }

  const M = new Array(s);

  if(CM) {
    for(let k = 0; k < s; k++) {
      const arr = new Array(s);
      for(let i = 0; i < s; i++) arr[i] = m[k + s * i];
      M[k] = [...arr, ...I[k]];
    }
  } else {
      for(let k = 0; k < s; k++) M[k] = [...m[k], ...I[k]];
  }
  
  const r = new Array(s);
  for(let k = 0; k < s; k++) r[k] = M[k];

  const s2 = s * 2;

  for(let k = 0; k < s; k++) {

    let [piv, ind] = [r[k][k], k];
    for (let i = k + 1; i < s; i++) {
      const f = r[i][k];
      if (Math.abs(f) > Math.abs(piv)) {
        piv = f;
        ind = i;
      }
    }
    if(failCheck(k, piv)) {
      const ret = new Array(s);
      for(let k = 0; k < s; k++) ret[k] = zrow;
      return ret;
    }

    if(ind) [r[k], r[ind]] = [r[ind], r[k]];
    const rpiv = 1 / piv;
    const f = new Array(s);
    for (let i = 0; i < s; i++) f[i] = r[i][k];

    for (let i = 0; i < s2; i++) {
      const m = r[k][i] = r[k][i] * rpiv;
      for (let j = 0; j < s; j++) {
        if(j == k) continue;
        r[j][i] -= m * f[j];
      }
    }

  }
  
  const ret = new Array(s);
  for(let k = 0; k < s; k++) ret[k] = r[k].slice(s, s2);
  return ret;
};

\$\endgroup\$
1
  • \$\begingroup\$ You might consider using the Bareiss algorithm which handles poorly-conditioned matrices better. Not sure if this is in-scope here or not. \$\endgroup\$
    – Charles
    Commented Mar 8, 2023 at 15:33

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.