Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Problem with mpow and simple comment #196

Open
iampi31415 opened this issue Mar 8, 2025 · 0 comments
Open

Problem with mpow and simple comment #196

iampi31415 opened this issue Mar 8, 2025 · 0 comments

Comments

@iampi31415
Copy link

iampi31415 commented Mar 8, 2025

I've read the interesting code for mpow but there could be a few bugs.

In this case, the identity is returned:

> a = new Matrix([[1,2],[3,4]])
> a.mpow(4)
Matrix {
  [
    1        0       
    0        1       
  ]
//...
}

Same happens: .mpow(1) (not that is useful), .mpow(2) and all perfect powers (powers of 2), so mpow(8) fails as well. It does not happen with .mpow(3).

Possible solutions (but I could be irrational):

  1. This line should use >= instead, and all previous problems are fixed.
  2. It seems that this line makes it inefficient: an extra product is calculated even when it's not used. Given that mmul is expensive, I'd simply test that e/2 >= 1 again, before running the product.

So something like from this:

    for (let e = scalar; e > 1; e /= 2) {
       if ((e & 1) !== 0) {
         result = result.mmul(bb);
       }
       bb = bb.mmul(bb);
     }

To this:

    for (let e = scalar; e >= 1; e /= 2) { // >=1 ensures running for 'evens'
       if ((e & 1) !== 0) {
         result = result.mmul(bb);
       }
       if (e/2 >=1){ // since it wont run otherwise
           bb = bb.mmul(bb);
        }
     }

So if a user uses 7, it runs A, AA, 3.5, then A^3,(AA)^2, 1.75, A^7, (AA)^4 And it skips running (AA)^4 which is not needed since A^3 * A^4 is the result.

I'm not doing a PR since my knowledge of this method is limited and there may be other edge cases, but that plus robust tests may help.


Comment

I think the library may benefit from these missing methods:

  1. Back substitution (it's partially implemented within some decompositions, but I'm unsure whether it's complete),
  2. Forward Substitution (same here)
  3. Symmetric multiplication (which would speed up some of your dependent libraries.)

The reason for 1 and 2 is that it would allows you to invert any triangular matrix, the reason for 3 is computing the normal matrix (which can be done in half the time.)

I'd also use _ (underscore) for methods that mutate the input matrix, since it's hard to remember it otherwise, but that may be a hard choice.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant