Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Intel Community
- Software
- Software Development SDKs and Libraries
- Intel® oneAPI Math Kernel Library
- polynomial evaluation

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

Anirudh

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

06-25-2013
02:36 PM

130 Views

polynomial evaluation

Link Copied

8 Replies

TimP

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

06-25-2013
08:33 PM

130 Views

I don't think you gave enough information to indicate why you would consider MKL or IPP for this. A macro expression such as

a[0] + x * (a[1] +x * a[2] + x*x * (a[3] + x * a[4]))

should be sufficient.

Gennady_F_Intel

Moderator

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

06-25-2013
08:45 PM

130 Views

there are no such functions neither in MKL or IPP which make polynomials calculations. Tim gave you good example how you can compute it.

in the case if the inputs would be vectors, then you can reuse some of VML functions for that.

Anirudh

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

06-26-2013
07:16 AM

130 Views

Thanks for the insight. I was looking for polynomial evaluation, because i was trying to implement 2D interpolation, such that i can interpolate using Cubic splines. There i would have to evaluate cubic polynomials. I could not use functions in image processing library (I believe) because they offer me evaluating the 2D at specific intervals. My new coordinates which i want to interpolate at are randomly placed in the original xy grid.

Do you think there is some function that can do the 2D interpolation for such a case ?

Andrey_N_Intel

Employee

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

06-26-2013
07:26 AM

130 Views

Hello,

Present version of Intel(R) MKL supports 1D spline based interpolation only. Data Fitting component of the library provides routines for spline construction and relevant computations such as interpolation, search and integration. We support linear, quadratic, cubic and user-defined splines.

Are you interested entirely in 2D interpolation, or 1D is also of your use?

Also, can you please provide, if possible, additional details behind your usage model of 2D interpolation such as problem dimension, type of spline (only cubic or other types are possible as well), number of interpolation sites, data types (integer, floating-point), etc? Is 2D interpolation is a compute intensive part of your application?

Andrey

Anirudh

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

06-26-2013
08:35 AM

130 Views

We did try using the 1D spline from MKL and found that the speed up was about 2x from our implementation, for a case where we were evaluating 10k different points on the same spline. I think MKL is faster in the case where many points are to be evaluated on the same spline. If you evaluate just one point on each of the hundreds of splines then i dont get any advantage.

Right now in my application we have to evaluate 900 splines, 1 point at a time, in which case MKL was slower than our implementation. I cannot create a vector of input points to the splines, as I only get the points to be evaluated on the spline, after some other processing.

I my application splines evaluation are taking 40% of the time (analyzed via Parallel Studio analyzer). I have a 2D matrix of 900x11 elements. I create 900 splines with 11 knots. Every loop i need to evaluate one point on each spline.

I was thinking if I make it 2D interpolation (900x11 original grid) instead, I can evaluate all the 900 points with the same function call and get a speed up.

Andrey_N_Intel

Employee

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

06-27-2013
02:31 AM

130 Views

Thank you much for the addtional details. While your request about support of 2D case is valid for the further analysis, let me provide additional details about 1D case.

As you mention, performance advantages of Intel(R) MKL Data Fitting routines are observed in the vector case when number of interpolation sites is, say, at least several hundreeds.

We are also aware about importance of scalar case for applications, e.g., when number of interpolation sites is 1 and number of functions is 1.

For those reasons in Intel(R) MKL 11.0. Update 2 we improved performance of interpolation routines for a scalar case, in particular speed of search and polynomial computations. As the interface overheads related to testing of function parameters are visible on small problem dimensions, we also added support of parameter DF_CHECK_FLAG in editor dfiEditVal. When disabled with the editor this flag helps to avoid extra parameter checks; by default this flag is enabled. However, please use this flag carefully, after you complete development/debuging of your code. See additional details in Release Notes http://software.intel.com/en-us/articles/intel-mkl-110-release-notes/ and Data Fitting Chapter of Intel(R) MKL Manual. But still, in the scalar case interface overheads may be visible.

Did you try the latest Intel(R) MKL 11.0 to test performance of the interpolation functions in the scalar case? If yes, did it help you in the scalar case?

API of Data Fitting component supports different use cases, including parallelization on level of the user's application.

As your application uses 900 independent splines I wounder if you apply parallelization in your interpolation code?

Something like this:

double breaks[900*11];

double sites[900];

#pragma omp parallel for

for ( i = 0; i < 900; i++ )

{

DFTaskPtr task;

status = dfdNewTask1D( &task, 11, &breaks[i*11], xhint, ny, y, yhint );

status = dfdEditPPSpline1D(...);

status = dfiEditVal(task, DF_CHECK_FLAG, DF_DISABLE_CHECK_FLAG );

status = dfdConstruct1D( task, DF_PP_SPLINE, DF_METHOD_STD );

status = dfdInterpolate1D( task, DF_INTERP, DF_METHOD_PP,1,&sites*, ...); status = dfDeleteTask( &task ); }*

If this loop is done inside of the other loop, the construction (and de-struction) of the Data Fitting task can be done once, outside of the inner loop. In the inner loop you either provide pointers to the new input parameters (e.g., breaks or/and function values) using relevant Data Fitting editors or copy the new values of input parameters into the same memory as before.

Please, let me know if this helps.

Andrey

Bernard

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

06-29-2013
05:04 AM

130 Views

TimP (Intel) wrote:

I don't think you gave enough information to indicate why you would consider MKL or IPP for this. A macro expression such as

a[0] + x * (a[1] +x * a[2] + x*x * (a[3] + x * a[4]))

should be sufficient.

It could be also vectorized when the input are scalar compnents of some vector.

SergeyKostrov

Valued Contributor II

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

06-30-2013
11:58 AM

130 Views

Topic Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page

For more complete information about compiler optimizations, see our Optimization Notice.