The Underground is the fastest way to do this. I know that you'll find a bunch lying around a couple of times as you travel from city to city, but to find more you'll need to dig them up. It really doesn't take too long
Here are a few tips for the underground.
First, go to the area on the map with the most flashing bits, so you don't have to go too far between attempts.
Take note of how many items it says are in the wall. Tap a few spots in different places. As soon as you see an item that isn't what you want, move on to the next one. For example if you see part of a sphere, just ignore it and look elsewhere. Or that damn heat rock, I got about 20 of those in my Diamond version :/
If you see part of a shard, carefully pick around it until you've uncovered it.
Once you have seen all the items that are in the wall, just bash one area with the big hammer to quit. For example if it says there are 3 items there, and you uncover 3 separate squares that are spheres, just quit that wall and move on.
I seem to recall shards being fairly common, e.g. at least 1/5 walls, maybe more.