Using a Z-matrix-like approach for generating new Cartesian coordinates from a new geometry defined in terms of delocalized internal coordinates, we eliminate the costly O(N-3) iterative back-transformation required in standard geometry optimizations using delocalized (or natural/redundant) internals, replacing it with a procedure which is only O(N). By replacing the gradient transformation with an iterative solution of a set of linear equations, we also reduce this step from O(N-3) to roughly O(N-2). This allows a very efficient method for geometry optimization of large molecules in internal coordinates. Several optimizations on systems containing up to 500 atoms are presented, comparing the performance of the new algorithm with its predecessor, and demonstrating the practical utility and efficiency of our approach.