I'm from the field of accelerator physics, specifically related to circular storage rings for synchrotron light sources. High energy electrons circulate around the ring, guided by magnetic fields. The electrons circulate billions of times and one wants to predict the stability. You can describe the motion of the electrons at one point in the ring in terms of phase space (position, momentum space). Each turn around the ring, the particle returns to a new position and momentum, and this defines a map in phase space called the "one-turn map". We may assume that there is a fixed point at the origin, and so it can be expanded in a power series. Thus, one wants to know about the stability of iterated power series maps. There are many hard questions about this, and the topic has an old history. Numerous libraries have been implemented- to implement so called Truncated Power Series Algebra. (See e.g. this paper about zlib by Y. Yan. More background on the physics and one approach to analysis is the normal form approach, e.g. Bazzani et. al. here.) The question is how to use such a library, and how to solve the stability problem. The main approach used in beam dynamics has been normal form analysis, which I don't believe has been successful. I wonder if some kind of spectral methods have been developed in other fields (perhaps along the lines of something like this?). Can someone think of another domain where the long term stability of iterated power series maps with a fixed point at the origin are analyzed, so we might share knowledge or get some fresh ideas? One example I know of is the work of Fishman and "Accelerator Modes" in atomic physics. Are there others? What other systems can be modeled as a kicked rotor, or a Henon map?
You probably know this already, but it sounds like something from the world of chaos theory and fractals? (hence it is computationally "difficult")
To your question, have you looked at the world of planetary mechanics and N-body problems? These are also forced to use iterative solutions, and the fundamental underlying physics is N^2, although the force sources are typically allowed to move around as well - just to complicate things further.
It is a long time since I've looked at them, but your mention of phase maps of stability sound very much like Henon Maps. I'm sure these must have wider applications, but they are usually described in terms of planetary stabilities (eg. the stability of a second moon in a planet-moon system).
You could look into asymptotic behavior of discrete Dynamical Systems. There is both a rich theoretical literature on this topic in mathematics and more applied literature in physics and computer science.