My quite large pile always freezes solid each winter. Once it thaws out I add the cleanings from my chicken coop to it (deep litter method) and turn it thoroughly. It'll be cooking again in just a day or two. It will be hard to jump start until it is thawed out.
ETA: If you can cover the pile with clear poly it will help thaw them faster then you can add some greens to jump start the process as soon as the piles are thawed.
I don't have any personal experience with this, but I wonder if you could build a small pile on top of your frozen one and cover them both. Then the heat from the mini might start to thaw the top of the other?
Not kidding, although I will do so indirectly, into partially used rabbit bedding, and apply to the composter after.
I have also greatly changed the composition of my compost this spring by adding a Flemish Giant rabbit to our household. She eats and poops a lot, and I use raw recycled paper wads as bedding, which worms love, so my system has been optimised to make best use of nitrogen. There's just so much carbon, what with paper rabbit bedding and stockpiled fall leaves.
I dig a hole down into the centre of the pile, add the freshest contributions, and that's where I get a nice hot compost. I don't touch the outer three or four inches of the pile, and it acts as insulation, and as a lower-temperature zone where the worms get a kickstart for the season. The undisturbed areas often form visible networks of myceliae before the compost starts to look soil-like.
My bin is one of those black plastic dealios that cities often hand out by request, so if the frozen pile in question is open to the air, I would tarp it in a dark coloured tarp.
I think that adding fresh material to the top of a frozen pile is a great idea to heat it up, as is adding lots of fluffy carbon to act as insulation. If it traps the heat generated by the fresh compost, it will thaw the rest of the pile. This is probably largely what happened in my case.
If it isn't cold enough outside to inhibit the composting action, and if you can keep it from getting that cold, it will continue to compost, and to make more heat.
A human being should be able to change a diaper, plan an invasion, butcher a hog, conn a ship, design a building, write a sonnet, balance accounts, build a wall, set a bone, comfort the dying, take orders, give orders, cooperate, act alone, solve equations, analyze a new problem, pitch manure, program a computer, cook a tasty meal, fight efficiently, die gallantly. Specialization is for insects.
-Robert A. Heinlein
I like the idea Chris brought up of digging a hole in the center of the frozen heap and filling that, I use spent coffee grounds and any greens I might have trimmed, then manures with bedding from the coop and some donkey manure go in.
This sort of combination (higher in N than you would normally use in a smaller space causes a heat up which thaws the heap from the inside out.
That means the most ready to activate bacteria and fungi come to life sooner than if you just waited for the heap to thaw on natures schedule.
I'd use the old compost pile as the primary ingredient in a new pile.
Gather sufficient quantities of browns and greens, mix them will with the ingredients of your old frozen pile, and watch it heat up. If it doesn't get hot, you need more greens. I'd suggest a couple of 5-gal. buckets of coffee grounds from a neighborhood coffee shop.
If its at all stinky, you'll need browns to absorb the moisture. I get a massive bag of shredded paper from work every couple of weeks. Mix it in well to get a lot of extra oxygen into the mix). That'll soak up the extra moisture, but I'd still add a lot of coffee grounds to get it hot.
"The rule of no realm is mine. But all worthy things that are in peril as the world now stands, these are my care. And for my part, I shall not wholly fail in my task if anything that passes through this night can still grow fairer or bear fruit and flower again in days to come. For I too am a steward. Did you not know?" Gandolf
Pretty cold place. It won't help you now that its still rock hard , but I have a great recommendation for you. In the run of the frost free season...
Dig out your compost pile, or make a new spot. Lay down a piece of rigid foam insulation( 1.5inch) . Then lay out a 40-50 foot heat tape/cable of the kind used for thawing gutters/ice on roofs.
This can be fastened to a piece of reinforcement mesh( a 4x8 sheet cost $8) using strip ties or wire. If your heap is 4x4 feet you can cut the mesh in half and lay the other half over the cable mesh. This will protect it from future digging.
Leave the power plug end out so easily connected and you can apply heat to your compost heap through the winter at night to keep it working or in the spring to "jump-start " it.
I use this technique all the time to keep my sand warm. In fact , still have it on under my sand at night . Just put a tarp over , or other half of your foam sheet if you make your pile 4x4 feet.
The foam., mesh( 6 inch squares) and heat tape are all available at Home Hardware , for ex.
You could put a bird on it...
If you don't have poultry, you could spread bird seed it, or a feeder, and or a bird house and attract wild birds. They will get the top layer going and gravity will help pull that down through the pile passively.
This is all just my opinion based on a flawed memory
No prison can hold Chairface Chippendale. And on a totally different topic ... my stuff:
Ernie and Erica Wisner's Rocket Mass Heater Everything Combo