if wordnet similarity is symmetric (i suspect it is) then you only need to compute half your matrix ( j = 1 - (# words-1), i = j+1 - # words ). additionally, because language follows the power law, it stands to chance that you are comparing some pairs of words more often. maybe you can keep a hash to check if you've seen a pair of words before, if so, you dont need to look it up. this? i dont know if this will gain you much, but maybe worth a try.

this is what i can think of for now. try profiling. that usually gives you an idea what to start with.

~downer