Algorithm for converting very large NFA to DFA
Have you tried Brzozowski's algorithm?  It's worst-case running time is exponential, but I see some references suggesting that it often performs very well, especially when starting with a NFA that you want to convert to a DFA and minimize.

The following paper seems relevant:


On the performance of automata minimization algorithms, Marco Almeida, Nelma Moreira, Rogerio Reis.


It evaluates a number of different algorithms for DFA minimization, including their application to your situation where we start with a NFA and want to convert it to a DFA and minimize it.

What does the strongly connected components (SCC) decomposition of your NFA (considering it as a directed graph) look like?  Does it have many components, where none of the components is too large?  If so, I wonder if it might be possible to devise a divide-and-conquer algorithm, where you take a single component, convert it from NFA to DFA and then minimize it, and then replace the original with the new determinized version.  This should be possible for single-entry components (where all edges into that component lead to a single vertex, the entry vertex).  I don't immediately see whether it would be possible to do something like this for arbitrary NFAs, but if you check what the structure of the SCC looks like, then you might be able to determine whether this sort of direction is worth exploring or not.