{"action":"opened","number":1540,"pull_request":{"url":"https://api.github.com/repos/chebfun/chebfun/pulls/1540","id":37849600,"html_url":"https://github.com/chebfun/chebfun/pull/1540","diff_url":"https://github.com/chebfun/chebfun/pull/1540.diff","patch_url":"https://github.com/chebfun/chebfun/pull/1540.patch","issue_url":"https://api.github.com/repos/chebfun/chebfun/issues/1540","number":1540,"state":"open","locked":false,"title":"Fix slow evaluation method for real-valued trigtechs","user":{"login":"gradywright","id":6304453,"avatar_url":"https://avatars.githubusercontent.com/u/6304453?v=3","gravatar_id":"","url":"https://api.github.com/users/gradywright","html_url":"https://github.com/gradywright","followers_url":"https://api.github.com/users/gradywright/followers","following_url":"https://api.github.com/users/gradywright/following{/other_user}","gists_url":"https://api.github.com/users/gradywright/gists{/gist_id}","starred_url":"https://api.github.com/users/gradywright/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gradywright/subscriptions","organizations_url":"https://api.github.com/users/gradywright/orgs","repos_url":"https://api.github.com/users/gradywright/repos","events_url":"https://api.github.com/users/gradywright/events{/privacy}","received_events_url":"https://api.github.com/users/gradywright/received_events","type":"User","site_admin":false},"body":"The `trigtech/feval` method is noticeably slower than `chebtech/feval` (up to two-times for scalar-valued functions and more for array-valued functions) for similar length real-valued functions.  The issue stems from the use of complex arithmetic in the `trigtech` evaluation routine, which is just standard Horner's method with the polynomial `z=exp(1i*pi*x)`.\r\n\r\nThis branch implements Horner's method for evaluating real-valued and complex-valued `trigtechs`.  The code (now contained in `horner.m`) checks if the `trigtech` is real and calls the method for doing all computations in real floating point arithmetic.  There are also different routines for array-valued real/complex `trigtech's` to optimize the computations.\r\n\r\nThe most noticeable difference in speed comes when evaluating an array-valued, real-valued, `trigtech` (something that occurs quite often in `chebfun2`).  For example:\r\n```\r\n>> rv = rand(1,100);\r\n>> x = rand(100,1);\r\n>> f_op = @(x) abs(sin(x-0.3)).^3;\r\n>> f = chebfun(f_op,[-pi pi],'trig')*rv;\r\n```\r\nOn the development branch, I get the following on my MacBook Pro:\r\n```\r\n>> tic, val = f(x); toc\r\nElapsed time is 0.405161 seconds.\r\n```\r\nWith the new code, I now get:\r\n```\r\n>> tic, val = f(x); toc\r\nElapsed time is 0.230274 seconds.\r\n```\r\nI have generally seen speed-ups in the range of 1.5 to about 2 with the new code.\r\n\r\nI also tried implementing Clenshaw's method for summing a Fourier series in order to make the evaluation code of a `trigtech` as fast as that as a `chebtech`.  While this method does indeed speed up the code to the level of `chebtech`, it turns out to be unstable for certain ranges of the input (see for example, A. C. R. Newbery, \"Error analysis for Fourier series evaluation.\" Mathematics of Computation 27.123 (1973): 639-644).  The attached plot illustrates this instability by comparing a few evaluation techniques for the function: `f = @(x) exp(cos(1e4*pi*(x-0.35)))`.  The plot shows the difference between evaluating `f` and evaluating the `trigfun` and `chebfun` versions. \r\n\r\n![accuracycomparison](https://cloud.githubusercontent.com/assets/6304453/8196039/97d1a4b2-1444-11e5-8ade-68404a022411.png)\r\n\r\nThere are ways to fix this instability (see referenced article above), but the logic involved in implementing this would seem to diminish any speed-ups.  However, I did not check to see if this would indeed be the case.\r\n","created_at":"2015-06-16T22:39:47Z","updated_at":"2015-06-16T22:39:47Z","closed_at":null,"merged_at":null,"merge_commit_sha":null,"assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/chebfun/chebfun/pulls/1540/commits","review_comments_url":"https://api.github.com/repos/chebfun/chebfun/pulls/1540/comments","review_comment_url":"https://api.github.com/repos/chebfun/chebfun/pulls/comments{/number}","comments_url":"https://api.github.com/repos/chebfun/chebfun/issues/1540/comments","statuses_url":"https://api.github.com/repos/chebfun/chebfun/statuses/5f5a509bcb5d03f97e64b896c459ccc01e9331a8","head":{"label":"chebfun:fix-slow-trigtech-feval","ref":"fix-slow-trigtech-feval","sha":"5f5a509bcb5d03f97e64b896c459ccc01e9331a8","user":{"login":"chebfun","id":3082993,"avatar_url":"https://avatars.githubusercontent.com/u/3082993?v=3","gravatar_id":"","url":"https://api.github.com/users/chebfun","html_url":"https://github.com/chebfun","followers_url":"https://api.github.com/users/chebfun/followers","following_url":"https://api.github.com/users/chebfun/following{/other_user}","gists_url":"https://api.github.com/users/chebfun/gists{/gist_id}","starred_url":"https://api.github.com/users/chebfun/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/chebfun/subscriptions","organizations_url":"https://api.github.com/users/chebfun/orgs","repos_url":"https://api.github.com/users/chebfun/repos","events_url":"https://api.github.com/users/chebfun/events{/privacy}","received_events_url":"https://api.github.com/users/chebfun/received_events","type":"Organization","site_admin":false},"repo":{"id":7893220,"name":"chebfun","full_name":"chebfun/chebfun","owner":{"login":"chebfun","id":3082993,"avatar_url":"https://avatars.githubusercontent.com/u/3082993?v=3","gravatar_id":"","url":"https://api.github.com/users/chebfun","html_url":"https://github.com/chebfun","followers_url":"https://api.github.com/users/chebfun/followers","following_url":"https://api.github.com/users/chebfun/following{/other_user}","gists_url":"https://api.github.com/users/chebfun/gists{/gist_id}","starred_url":"https://api.github.com/users/chebfun/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/chebfun/subscriptions","organizations_url":"https://api.github.com/users/chebfun/orgs","repos_url":"https://api.github.com/users/chebfun/repos","events_url":"https://api.github.com/users/chebfun/events{/privacy}","received_events_url":"https://api.github.com/users/chebfun/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/chebfun/chebfun","description":"Chebfun is an open-source software system for numerical computing with functions.","fork":false,"url":"https://api.github.com/repos/chebfun/chebfun","forks_url":"https://api.github.com/repos/chebfun/chebfun/forks","keys_url":"https://api.github.com/repos/chebfun/chebfun/keys{/key_id}","collaborators_url":"https://api.github.com/repos/chebfun/chebfun/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/chebfun/chebfun/teams","hooks_url":"https://api.github.com/repos/chebfun/chebfun/hooks","issue_events_url":"https://api.github.com/repos/chebfun/chebfun/issues/events{/number}","events_url":"https://api.github.com/repos/chebfun/chebfun/events","assignees_url":"https://api.github.com/repos/chebfun/chebfun/assignees{/user}","branches_url":"https://api.github.com/repos/chebfun/chebfun/branches{/branch}","tags_url":"https://api.github.com/repos/chebfun/chebfun/tags","blobs_url":"https://api.github.com/repos/chebfun/chebfun/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/chebfun/chebfun/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/chebfun/chebfun/git/refs{/sha}","trees_url":"https://api.github.com/repos/chebfun/chebfun/git/trees{/sha}","statuses_url":"https://api.github.com/repos/chebfun/chebfun/statuses/{sha}","languages_url":"https://api.github.com/repos/chebfun/chebfun/languages","stargazers_url":"https://api.github.com/repos/chebfun/chebfun/stargazers","contributors_url":"https://api.github.com/repos/chebfun/chebfun/contributors","subscribers_url":"https://api.github.com/repos/chebfun/chebfun/subscribers","subscription_url":"https://api.github.com/repos/chebfun/chebfun/subscription","commits_url":"https://api.github.com/repos/chebfun/chebfun/commits{/sha}","git_commits_url":"https://api.github.com/repos/chebfun/chebfun/git/commits{/sha}","comments_url":"https://api.github.com/repos/chebfun/chebfun/comments{/number}","issue_comment_url":"https://api.github.com/repos/chebfun/chebfun/issues/comments{/number}","contents_url":"https://api.github.com/repos/chebfun/chebfun/contents/{+path}","compare_url":"https://api.github.com/repos/chebfun/chebfun/compare/{base}...{head}","merges_url":"https://api.github.com/repos/chebfun/chebfun/merges","archive_url":"https://api.github.com/repos/chebfun/chebfun/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/chebfun/chebfun/downloads","issues_url":"https://api.github.com/repos/chebfun/chebfun/issues{/number}","pulls_url":"https://api.github.com/repos/chebfun/chebfun/pulls{/number}","milestones_url":"https://api.github.com/repos/chebfun/chebfun/milestones{/number}","notifications_url":"https://api.github.com/repos/chebfun/chebfun/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/chebfun/chebfun/labels{/name}","releases_url":"https://api.github.com/repos/chebfun/chebfun/releases{/id}","created_at":"2013-01-29T13:59:55Z","updated_at":"2015-06-07T19:41:54Z","pushed_at":"2015-06-16T22:39:47Z","git_url":"git://github.com/chebfun/chebfun.git","ssh_url":"git@github.com:chebfun/chebfun.git","clone_url":"https://github.com/chebfun/chebfun.git","svn_url":"https://github.com/chebfun/chebfun","homepage":"http://www.chebfun.org/","size":34846,"stargazers_count":45,"watchers_count":45,"language":"Matlab","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":8,"mirror_url":null,"open_issues_count":166,"forks":8,"open_issues":166,"watchers":45,"default_branch":"development"}},"base":{"label":"chebfun:development","ref":"development","sha":"8a3957c293da01ed8a60279553f0a431d853bec2","user":{"login":"chebfun","id":3082993,"avatar_url":"https://avatars.githubusercontent.com/u/3082993?v=3","gravatar_id":"","url":"https://api.github.com/users/chebfun","html_url":"https://github.com/chebfun","followers_url":"https://api.github.com/users/chebfun/followers","following_url":"https://api.github.com/users/chebfun/following{/other_user}","gists_url":"https://api.github.com/users/chebfun/gists{/gist_id}","starred_url":"https://api.github.com/users/chebfun/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/chebfun/subscriptions","organizations_url":"https://api.github.com/users/chebfun/orgs","repos_url":"https://api.github.com/users/chebfun/repos","events_url":"https://api.github.com/users/chebfun/events{/privacy}","received_events_url":"https://api.github.com/users/chebfun/received_events","type":"Organization","site_admin":false},"repo":{"id":7893220,"name":"chebfun","full_name":"chebfun/chebfun","owner":{"login":"chebfun","id":3082993,"avatar_url":"https://avatars.githubusercontent.com/u/3082993?v=3","gravatar_id":"","url":"https://api.github.com/users/chebfun","html_url":"https://github.com/chebfun","followers_url":"https://api.github.com/users/chebfun/followers","following_url":"https://api.github.com/users/chebfun/following{/other_user}","gists_url":"https://api.github.com/users/chebfun/gists{/gist_id}","starred_url":"https://api.github.com/users/chebfun/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/chebfun/subscriptions","organizations_url":"https://api.github.com/users/chebfun/orgs","repos_url":"https://api.github.com/users/chebfun/repos","events_url":"https://api.github.com/users/chebfun/events{/privacy}","received_events_url":"https://api.github.com/users/chebfun/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/chebfun/chebfun","description":"Chebfun is an open-source software system for numerical computing with functions.","fork":false,"url":"https://api.github.com/repos/chebfun/chebfun","forks_url":"https://api.github.com/repos/chebfun/chebfun/forks","keys_url":"https://api.github.com/repos/chebfun/chebfun/keys{/key_id}","collaborators_url":"https://api.github.com/repos/chebfun/chebfun/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/chebfun/chebfun/teams","hooks_url":"https://api.github.com/repos/chebfun/chebfun/hooks","issue_events_url":"https://api.github.com/repos/chebfun/chebfun/issues/events{/number}","events_url":"https://api.github.com/repos/chebfun/chebfun/events","assignees_url":"https://api.github.com/repos/chebfun/chebfun/assignees{/user}","branches_url":"https://api.github.com/repos/chebfun/chebfun/branches{/branch}","tags_url":"https://api.github.com/repos/chebfun/chebfun/tags","blobs_url":"https://api.github.com/repos/chebfun/chebfun/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/chebfun/chebfun/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/chebfun/chebfun/git/refs{/sha}","trees_url":"https://api.github.com/repos/chebfun/chebfun/git/trees{/sha}","statuses_url":"https://api.github.com/repos/chebfun/chebfun/statuses/{sha}","languages_url":"https://api.github.com/repos/chebfun/chebfun/languages","stargazers_url":"https://api.github.com/repos/chebfun/chebfun/stargazers","contributors_url":"https://api.github.com/repos/chebfun/chebfun/contributors","subscribers_url":"https://api.github.com/repos/chebfun/chebfun/subscribers","subscription_url":"https://api.github.com/repos/chebfun/chebfun/subscription","commits_url":"https://api.github.com/repos/chebfun/chebfun/commits{/sha}","git_commits_url":"https://api.github.com/repos/chebfun/chebfun/git/commits{/sha}","comments_url":"https://api.github.com/repos/chebfun/chebfun/comments{/number}","issue_comment_url":"https://api.github.com/repos/chebfun/chebfun/issues/comments{/number}","contents_url":"https://api.github.com/repos/chebfun/chebfun/contents/{+path}","compare_url":"https://api.github.com/repos/chebfun/chebfun/compare/{base}...{head}","merges_url":"https://api.github.com/repos/chebfun/chebfun/merges","archive_url":"https://api.github.com/repos/chebfun/chebfun/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/chebfun/chebfun/downloads","issues_url":"https://api.github.com/repos/chebfun/chebfun/issues{/number}","pulls_url":"https://api.github.com/repos/chebfun/chebfun/pulls{/number}","milestones_url":"https://api.github.com/repos/chebfun/chebfun/milestones{/number}","notifications_url":"https://api.github.com/repos/chebfun/chebfun/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/chebfun/chebfun/labels{/name}","releases_url":"https://api.github.com/repos/chebfun/chebfun/releases{/id}","created_at":"2013-01-29T13:59:55Z","updated_at":"2015-06-07T19:41:54Z","pushed_at":"2015-06-16T22:39:47Z","git_url":"git://github.com/chebfun/chebfun.git","ssh_url":"git@github.com:chebfun/chebfun.git","clone_url":"https://github.com/chebfun/chebfun.git","svn_url":"https://github.com/chebfun/chebfun","homepage":"http://www.chebfun.org/","size":34846,"stargazers_count":45,"watchers_count":45,"language":"Matlab","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":8,"mirror_url":null,"open_issues_count":166,"forks":8,"open_issues":166,"watchers":45,"default_branch":"development"}},"_links":{"self":{"href":"https://api.github.com/repos/chebfun/chebfun/pulls/1540"},"html":{"href":"https://github.com/chebfun/chebfun/pull/1540"},"issue":{"href":"https://api.github.com/repos/chebfun/chebfun/issues/1540"},"comments":{"href":"https://api.github.com/repos/chebfun/chebfun/issues/1540/comments"},"review_comments":{"href":"https://api.github.com/repos/chebfun/chebfun/pulls/1540/comments"},"review_comment":{"href":"https://api.github.com/repos/chebfun/chebfun/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/chebfun/chebfun/pulls/1540/commits"},"statuses":{"href":"https://api.github.com/repos/chebfun/chebfun/statuses/5f5a509bcb5d03f97e64b896c459ccc01e9331a8"}},"merged":false,"mergeable":null,"mergeable_state":"unknown","merged_by":null,"comments":0,"review_comments":0,"commits":5,"additions":355,"deletions":46,"changed_files":5}}