PARI/GP中矩阵幂运算采用何种算法？计算复杂度是多少？

你好，关于你询问的PARI/GP中矩阵幂运算的相关问题，这里有明确的结论：

• 使用的算法：采用的是重复平方算法（binary powering，即快速幂算法），这是一种通过平方操作来大幅减少乘法次数的高效幂运算方法。
• 计算复杂度：以幂次n为参考，算法的时间复杂度为O(log n)（这里指的是矩阵乘法的执行次数）。如果结合矩阵本身的规模来看，比如对于k×k的矩阵，单次矩阵乘法的复杂度为O(k³)，那么整体的运算复杂度就是O(k³ log n)。

这个结论来自PARI/GP的核心开发者Bill Allombert的说明，之前确实很难在公开网络资料里找到明确提及，现在这个疑问已经解决啦。

内容的提问来源于stack exchange，提问作者Pedja