> Is it possible to substantially increase Ruby's execution speed by
> compiling it to an EXE file?

Execution speed will not be increased very much by this method.
The binary executable will still contain a copy of the ruby interpreter
which will run the ruby code much the same way as the original.

> I think I heard about a project somewhere that's like Jython, which can
> compile Ruby to Java bytecode. If that exists, then, one could compile
> the Java bytecode to an optimized native executable using GCJ or another
> commercial Java bytecode to EXE tool.

It's called JRuby.  It's not a Ruby-to-Java compiler, but a ruby
interpreter written in Java.

Even if you compiled to Java:

1) Java is not very fast anyways.
2) Compiling Java to an executable has the same problems I described above.

Do not despair, for there is yet one alternative:

Most programs follow the 80/20 rule.  That is, 80% of the time is spent in
20% of the code.  If this is your situation, you can optimize the
time-critical portion of your code by writing it in C, and making it a
ruby extension.  This portion of the code will run at the original C
speed.  Depending on the problem at hand, you might see dramatic
improvements in execution.

I've glanced at the Ruby API, and it looks very easy to use.  I suggest
you consider this option.

Cheers,
Daniel.