I'd start by powering them separately. That way you can connect the Arduino to your PC for code downloading and not have to worry about it. The 5V regulator can only supply some hundreds of mA for itself and a few low current devices, not the tens of Amps your LEDs will use.
Connect the Gnd of the LED strips to the Gnd of the Arduino.
You may find you need to connect 5V from your big supply to both ends of the LED strips, and perhaps in their middle as well, to achieve uniform brightness.
Once you have achieved stable operation, you can power the Arduino via the 5V/Gnd connections on its power header and use it disconnected from the PC.