0
$\begingroup$

I come from Computer Science and I designed an algorithm belongs to Numerical Linear Algebra field. The analysis of algorithms in Computer Science usually involves the correctness, time and space complexity.

Some one told me this algorithm is presentable and publishable as a paper if you can prove that it is numerically stable. Some thing we have never done before and I don't know where to start from!. All I know is if I impose some perturbation to variables, the results must be good!

The algorithm involves a for loop, in each loop it computes determinant of a symmetric Jacobi matrix and it has some plus and minus and power 2 and division operations.

How can I show that this algorithm is numerically stable?

I am not sure if this information is enough, if any other thing is needed I will provide it.

Thanks in advance.

$\endgroup$
  • $\begingroup$ Implement it in some system with multiple precision and compute some examples with very high precision and with IEEE double-precision and see how large is the difference between the two. $\endgroup$ – logarithm May 10 at 19:44
  • $\begingroup$ Alternatively, implement it using some interval arithmetic library and check how large intervals get compared to the input intervals. $\endgroup$ – logarithm May 10 at 19:46
  • $\begingroup$ @logarithm Thanks for your reply, Are the mentioned methods presentable in a mathematics journal as a proof? $\endgroup$ – No one May 10 at 20:25
  • $\begingroup$ As the algorithm becomes more complicated it is harder to produce actual bounds for the error. When that is the case, people do publish experimental results. $\endgroup$ – logarithm May 10 at 20:34
  • $\begingroup$ My work is close to paper Inverse spectral problem for pseudo-Jacobi matrices with partial spectral data in sciencedirect.com/science/article/pii/S0377042715005567 . The author did exactly what you said. Thanks $\endgroup$ – No one May 11 at 0:38
1
$\begingroup$

Let me first give an intuitive description of numerical instability: it is the possibility for round-off errors to get so amplified as to contaminate the results.

Numerical stability is a guarantee that there will be no numerical instability.

Here is a lecture on round-off errors from a course on numerical linear algebra. It uses the concept of a condition number.

If these are insufficient, you will need the involvement of a person who can analyze your algorithm for numerical stability--make them co-author?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.