I have so-far tried all ways of computing kendall tau significance (where there are ties) described.
However, none of them works good, even for relatively large vectors. I think the problem is in general it seems that these methods tend to overestimate the statistical significance of data, so are there any alternative ways to compute kendall tau's significance? (at least get some degree of tie-adjustments)?
Best Answer
Note that since the denominator only depends on the margins, not on the association, the exact permutation p-value is the same for any of the statistics that has $N_c-N_d$ on the numerator (Kendall's tau, tau-b, tau-c, Somer's-D etc).
There are algorithms for computing p-values of all these measures of association for ordinal data efficiently, by taking account of the ordering of the permutations induced by some simple form of the test statistic, and only considering the ones more extreme than the test statistic (or considering as few additional ones as possible), generally arising from ideas based on Mehta and Patel's networking algorithm, though there have been developments and ideas from many authors.
Some stats packages implement such algorithms. It might be worth checking whether some of the exact-test related packages already have an efficient version of it for some version of the Kendall statistic.
For example, I believe SPSS Exact Tests has this implemented for the Kendall tau.
(Out of curiosity, why would it matter for you if you were only able to get a probabilistic bound on the p-value using resampling? How does (say) knowing the p-value is almost certainly less that $3.2 \times 10^{-5}$ rather than computing it to be exactly $1.6245 \times 10^{-6}$? What additional information does that give you?)