# Least squares method for general formula

Up today I've only been using Least squares method in "standard" applications like power/inverse/linear regression with known formulas.

But now I'd like to use it to calibrate (i.e. determine some coefficients) following model:

$$T(nprocs, DOF) = \alpha \cdot DOF^\beta + \gamma \cdot \frac{DOF^\delta}{nprocs}$$

I want to use following data for calibration:

From the table we can see, that

\begin{align} nprocs &\in \{1,2,3,4,6,8,12,24\}\\ DOF &\in \{3993, 7623, 11253, 14883, 18513\}. \end{align}

It implies, that we'll have an overdetermined system of 40 equations like this:

\begin{align} 0.656395 &= \alpha \cdot 3993^\beta + \gamma \cdot \frac{3993^\delta}{1}\\ 0.2569141 &= \alpha \cdot 3993^\beta + \gamma \cdot \frac{3993^\delta}{2}\\ &\vdots\\ 0.407449 &= \alpha \cdot 11253^\beta + \gamma \cdot \frac{11253^\delta}{4}\\ &\vdots\\ 0.373136 &= \alpha \cdot 18513^\beta + \gamma \cdot \frac{18513^\delta}{24} \end{align}

If the system was small, I'd just assemble a function $LS$ like this $$LS(\alpha, \beta, \gamma, \delta) = (0.656395 - (\alpha \cdot 3993^\beta + \gamma \cdot \frac{3993^\delta}{1}))^2 + (0.2569141 - (\alpha \cdot 3993^\beta + \gamma \cdot \frac{3993^\delta}{2}))^2 + \cdots$$

and then I'd make partial derivatives and minimize the system by making them equal to zero.

The problem is, apparently, that here I can't use this method, because the system is too large. I suppose, that it'll go to assembling a quadratic polynomial like this

$$x^TAx + b^Tx + c$$

where $A$ will be a symmetric, positive-definite matrix and so I'll be able to minimize the polynomial by solving the simple system $$Ax = b.$$

My question is - what's the best way to get the matrix $A$ and the vector $b$ without having to assemble the whole function (polynomial) $LS$?

For this problem, you need, in principle, nonlinear regression or turn the problem into an optimization problem.

But, you already have good estimates of the parameters (after the first step you posted). So, why not to solve the problem using Newton-Raphson for four equations (the derivatives with respect to $\alpha,\beta,\gamma,\delta$ which are equal to zero) for the same four unknowns.

You could even compute the derivatives using finite differences (this is what I would suggest). All of this could be done using Excel.

Edit

In order to prepare our discussion on chat, let us consider what you started with here. For $A$ and $B$, you had a table of $n$ data points $(x_i,y_i)$ and you wanted to fit according to model $$y=a x^b$$ You can easily get estimates fo the parameters using a logarithm transform $$\log(y)=\log(a)+b \log(x)=c+b\log(x)$$ and a linear regression based on data points $(\log(x_i),\log(y_i))$ gives the estimates of $(c,b)$ and $a=e^c$. Eventually, if you want a better fit, you could use the method described here.

But, since what is measured is $y$ and not any of its possible transforms, you need to continue using nonlinear regression; the goal of it will be to minimize $$F=\frac 12\sum_{i=1}^n(ax_i^b-y_i)^2$$ If you do not access a nonlinear regression tool (remember that you could use Excel solver), let us write the conditions of the minimum which is $F'_a=0$ and $F'_b=0$. Let use write these conditions $$F'_a=\sum_{i=1}^n x_i^b(ax_i^b-y_i)=0\implies a\sum_{i=1}^n x_i^{2b}-\sum_{i=1}^n x_i^by_i=0\tag 1$$ $$F'_b=\sum_{i=1}^n a x_i^b \log (x_i) \left(a x_i^b-y_i\right)=0\implies a\sum_{i=1}^n x_i^{2b}\log(x_i)-\sum_{i=1}^n x_i^b \log(x_i)y_i=0\tag 2$$ So, we have two nonlinear equations in $(a,b)$ which, for commodity, I shall rewrite as $$f(a,b)=a\sum_{i=1}^n x_i^{2b}-\sum_{i=1}^n x_i^by_i=0\tag 3$$ $$g(a,b)=a\sum_{i=1}^n x_i^{2b}\log(x_i)-\sum_{i=1}^n x_i^b \log(x_i)y_i=0\tag 4$$ Since we already have good estimates $a_0$ and $b_0$, we can use Newton-Raphson method to solve them writing $$f(a_0,b_0)+\frac {df(a,b)}{da}\Delta a+\frac {df(a,b)}{db}\Delta b=0 \tag 5$$ $$g(a_0,b_0)+\frac {dg(a,b)}{da}\Delta a+\frac {dg(a,b)}{db}\Delta b=0 \tag 6$$ the derivatives being computed at $a=a_0$ and $b=b_0$. These equations are linear. So, compute $(\Delta a,\Delta b)$ then $a=a0+\Delta a$, $b=b0+\Delta b$ and replace $a_0$ by $a$ and $b_0$ by $b$ until they do not change significantly.

You could even reduce the problem to a single equation if you notice that $a$ is explicitelt given from equation $(3)$ $$a=\frac{\sum_{i=1}^n x_i^by_i }{ \sum_{i=1}^n x_i^{2b}}$$ which makes equation $(4)$ to become $$\frac{\sum_{i=1}^n x_i^by_i }{ \sum_{i=1}^n x_i^{2b}}\sum_{i=1}^n x_i^{2b}\log(x_i)-\sum_{i=1}^n x_i^b \log(x_i)y_i=0\tag 7$$ which is a nonliear equation in $b$ (you can solve it using Newton method).

• I'd prefer not to use previous estimates, because I intend to use this formulas on other machines where coefficients can differ pretty dramatically. I'd like to transform the problem into the optimization one, but I wasn't lucky with that yet :-) Tomorrow I'll post my attempt. Nov 18 '16 at 22:41
• For the first part of the work, you generated discrete values for $A,B$. Thei individual curve fit does not make any problem. So, you have your good estimates. But, let see what you will post. Nov 19 '16 at 4:25
• Ok, I tried, but I'm stuck on a very basic thing - I'm not able to get the quadratic polynomial, because of the size of the system. I know, how to minimize it, when matrix $A$ is symmetric, positive-definite etc., but I'm simply not able to get it now. In school we've always deduced $Ax=b$ etc. from $LS$ polynomial. I hope it's clear what I wanted to say :-) Nov 19 '16 at 11:52
• Now I realized, that when those equations are not linear, maybe it's not the best way to try to "formulate" them into one quadratic function. But then I have no idea, how to apply any minimization technique... Nov 19 '16 at 12:38
• It is 7:00pm here. If you want, contact me around 7:00am and we could go and chat. Nov 19 '16 at 17:42