With those sorts of numbers you will do best drawing them to a BufferedImage (via direct access to the underlying int[])
You will take the constant time hit of a large software blitted image, but the individual pixel array accesses will be fast. (As fast as is possible in Java)
You should be able to reduce the expense of the large software blitted image, by ensuring the BufferedImage is in a pixel format that can be efficiently copied to the screens.(without the blitting routine having to perform pixel format conversion)
This can be achieved by using GraphicsConfiguration.createCompatibleImage.
However, this may mean you need to write several versions of the particle rasterizing code, to deal with each of the different possible pixel formats the returned BufferedImage may use.