<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
<br class="">
<div>
<blockquote type="cite" class="">
<div class="">On Aug 19, 2016, at 4:13 AM, Munson, Todd <<a href="mailto:tmunson@mcs.anl.gov" class="">tmunson@mcs.anl.gov</a>> wrote:</div>
<br class="Apple-interchange-newline">
<div class=""><br class="">
Hi!<br class="">
<br class="">
The only provable way to test for linearity of a function is using<br class="">
code analysis.<br class="">
<br class="">
A quick hack that should work okay is to evaluate the gradient at<br class="">
two (or more) random points and calculate the distance between<br class="">
the gradients. Note: this is not a good test for piecewise <br class="">
linear functions, as you would need the random points to<br class="">
lie in different regions to detect that the gradient is<br class="">
not constant.<br class="">
<br class="">
Something similar can be used for quadratics. Here you evaluate<br class="">
the Hessian at two random points. You really want to calculate<br class="">
the distance between the matrices. I did not find that method <br class="">
in the PETSc documentation. Therefore, I would compare the<br class="">
values of Hessian vector products, H1*y - H2*y where y is<br class="">
a random vector.<br class="">
</div>
</blockquote>
<div><br class="">
</div>
<div>You could call MatNorm (<a href="http://www.mcs.anl.gov/petsc/petsc-current/docs/manualpages/Mat/MatNorm.html" class="">http://www.mcs.anl.gov/petsc/petsc-current/docs/manualpages/Mat/MatNorm.html</a>), and use it to determine if, say, the infinity-norm
of the difference between the matrices is small.</div>
<div><br class="">
</div>
<div>Hessian vector products could also potentially work. I think there might be some papers on estimating matrix norms from matrix-vector products, but if I remember correctly the last time I looked this up, some of these algorithms require transposes and
may not be scalable.</div>
<br class="">
<blockquote type="cite" class="">
<div class=""><br class="">
These hacks really prove that the function is not linear or <br class="">
not quadratic, but cannot truly establish that the function<br class="">
is linear or quadratic.<br class="">
<br class="">
Todd.<br class="">
<br class="">
<blockquote type="cite" class="">On Aug 19, 2016, at 2:40 AM, Marco Zocca <<a href="mailto:zocca.marco@gmail.com" class="">zocca.marco@gmail.com</a>> wrote:<br class="">
<br class="">
How does a numerical method test for linearity (or in general order of<br class="">
nonlinearity) of an operator? By comparing function value with the<br class="">
first two Taylor terms, within machine precision?<br class="">
I suspect only code analysis ("reification", as in analysis of the<br class="">
expression syntax tree) would be feasible and reliable for general<br class="">
problems.<br class="">
</blockquote>
<br class="">
</div>
</blockquote>
</div>
<br class="">
</body>
</html>