Fast change of basis in algebras
Given an n-dimensional algebraA represented by a basisB and structure constants, and given a transformation matrix for a new basisC., we wish to compute the structure constants forA relative to C. There is a straightforward way to solve this problem inO(n5) arithmetic operations. However given an O(nω) matrix multiplication algorithm, we show how to solve the problem in time O(nω+1). Using the method of Coppersmith and Winograd, this yields an algorithm ofO(n3.376).
The final publication is available at Springer via https://doi.org/10.1007/BF01294835. Hentzel, Irvin Roy, and David Pokrass Jacobs. "Fast change of basis in algebras." Applicable Algebra in Engineering, Communication and Computing 3, no. 4 (1992): 257-261. doi:10.1007/BF01294835. Posted with permission.