The Navigation mesh relies on just a bit more than A* when you near the end of your point, or for optimizations. But yes, that's pretty much all there is to it. A* or what ever other graph search method you use is what drives it.
Grid A*'s are infinitely spanning grids that details the map. Normally the grids have uniform costs, but they can also have adjusted costs. Grids are generally more popular for point and click games, or stratergy based games as they make it incredibly easy to query data about the world.
By Matrix I assume you mean the adjacency matrix. There's no good answer here. It's just it depends. The cost of the adjacency matrix is more significant than the cost of an adjacency list. Or other graphing structures. The adjacency matrix is not designed to be sparse. But it does have it's uses. Memory look up on it is fast and predictable so cache misses are not so likely. But it's probable that you'd rather take the cost of speed than memory complexity.
But generally, before you think about efficiency. Just remember that standard A* generally isn't efficient to begin with with larger sets of data. The algorithm searches radially outwards... which means it's checking a lot more data than some other search queries for far away points.
As far as ACO algorithms go... it's implementation is worthless if you're not dealing with swarms of agents.
For optimizations. Generally Navigation is expensive all on it's own. Which is why it's often not so uncommon for developers to take short cuts.
For a lot of games that uses pure A*, it's because the actors do not have to travel far. This is seen a majority of the time with FPS games. The targets are mostly stationary... or only moving short distances. Their life span is only a few seconds.
For your games with more complex levels or larger worlds... they usually break it up. Forgo the use of A* completely and use a different search algorithm (The shortest path is often times not the best or the most realistic path). Or very literally teleport agents around the map.
