ukmuiik

Question

TL;DR: I developed a way of solving systems of equations which is up to 25,000x faster than base methods. I want to publish but my advisor doesn't think it's worth it.

I work as a data scientist with hyperspectral data. In this area, we treat every single pixel as its own system of equations. Because of this, we need to solve potentially thousands of systems of equations. Obviously, if we use traditional tools this is exceptionally slow and potentially not worth our time. However, each problem is relatively small, think 1 variable with ~100 non-linear equations.

I came up with 2 separate systems to solve these equations much faster. The first one adapts MATLAB's fminbnd so that every single one of these problems can be solved at once. This allows the function evaluation to take advantage of vectorized processing which in many languages, particularly research based languages gives a drastic speedup. See the MATLAB codebase. In addition, this allowed us to use GPUs to solve the problem resulting in a much larger performance increase. All told, this allows us to have a ~300-1000x performance speedup.

The second system is meant for solving much larger systems of equations. This uses the same idea but with a Levenburg-Marquardt implementation. This utilizes MATLAB's pagefun and with an aggressive implementation, this beats out the best global solver I could find by a factor of 25,000 for the same results (this method also allowed me to obtain an order of magnitude improvement for my results with a 4000x speedup).

While these results are impressive, my advisor wants me to focus on my primary research and wants me to present those results. I'd like to present both results as I believe they are both valuable to the body of knowledge but my advisor has always been honest with me and I feel like I should follow his lead.

Should I publish this linear programming method despite my advisor's advice?

This has appeared in the review closure queue,and I'm voting to close for two reasons. 1. The details of your work are off-topic, as this SE is about academia, not mathematics or computer science. 2. That leaves a question of "should I do as my advisor says or not", and nobody can answer that as nobody knows the situation as well as you or your advisor. So it's an impossible question for this site. Good luck! — 7 hours ago
It's not that you're asking for math/programming help but, rather, that your question can only be answered by somebody with an in-depth knowledge of your specific area of study. Essentially, a large part of "should I publish this" boils down to an evaluation of your work. — 6 hours ago
On a tangent: The fact that you speak of a speedup of [some number] times in stead of a speedup as a function of the input (i.e. from O(n^10) to O(n^2), suggests that you have not researched your method thoroughly at all. Given the absolutely vast body of work on this very subject, I doubt you have something worth publishing at this point. It might turn out to be, after proper research, but it certainly doesn't seem like anything at all now. — 6 hours ago
@Servaes To somebody who's actually solving equations, a massive improvement in the constant hidden by big-O notation could be very significant. Asymptotic complexity isn't the only game in town. — 6 hours ago
Are you really sure that what you're doing is novel? This is the question you need to ask when publishing. It sounds like the science is your field of expertise and not the algorithms. While your solution is perhaps faster than the solvers you have tried, that's not evidence that it is not known in the literature. Did you do a literature review to make sure this is truly a novel approach and not just fiddling with implementation? From what you've described, I'm guessing the answer is no. — 4 hours ago

Buffy 8,90433448 · Accepted Answer · 2018-08-05 17:22:54Z

It is good to have publications. It is also good to follow the advice of your advisor for many reasons. Advisors have some say over your future, of course, so caution is indicated, at least, in every case.

Note first that it has been many years since I was current with the algorithms of integer and linear programming. I suspect you are more current and your advisor more so, so be a bit careful in analyzing what I say below.

The field in general is quite mature and the existing algorithms are very sophisticated. This was true 30 year ago, in fact. If the field has settled down since then there is little urgency in publishing now, as it is unlikely that you would be beaten to publication if you wait. You can make your advisor happy and, indeed, make progress on your main work without abandoning what you have.

However, I think that a real advance should be questioned and you should be the one to question it. In particular, it may be that the reason for such good results is that your specific problem has characteristics that make this possible and your algorithm is nicely tailored to a special case. The possibility of that actually opens a door for your future work. If it is true, then knowing and describing that special case would be very useful, along with the algorithm.

Also, if it is, indeed, a special case and you have tested only with the confines of this case then your results may not apply generally. It would be good to know, before you publish, whether this is true or not. And it would be especially good for you if you are the one to discover this. Fortunately, you can test your algorithm on a wider class of problems found in the literature. Thus, you can, perhaps, rule out the situation in which you have an anomaly. But your primary work should likely come first.

Thank you, the main reason I'm unsure is that I'm not talking about the algorithm itself but rather the idea that linear programming can be vectorized for cases in which the function evaluation can be vectorized. Currently, there are ~10 functions I'm working with and this ideology applies to all of them largely because I am using traditional methods developed 50 years ago but in a way that makes them incredibly fast on modern computers. You are right though, I should respect my advisor for a variety of reasons while also testing the viability and usefulness of my method. — 10 hours ago
@Durkee, there have been a lot of books since, but 25 years ago, I found this book to be indispensable on the algorithms. amazon.com/Linear-Programming-Books-Mathematical-Sciences/dp/â€¦ — 9 hours ago
I prefer GÃ¤rtner and MatouÃ…Â¡ek for theory and geometric intuition and Vanderbei for the (baseline) practical details. — 9 hours ago

Oleg Lobachev 2,9311017 · Answer 2 · 2018-08-05 17:53:53Z

I do not know, who is "right". Your contributions look quite impressive, though. So I am trying here to come up with arguments that might lead your supervisor to his/her decision. I deliberately omit politics and strategising.

Your new method seems to work very well on your data. Does it work well enough on other kinds of data? It might be the nature of your data that allows for such speedups. While this would still be of interest for your actual narrow topic, it might not qualify as a broad solution.

You use MatLab. This is probably the correct tool for you to use. This might be not the right tool for the general claim. (In other words, you'd be more or less desk-rejected if you present your MatLab solution to the specialists in linear programming. I am not sure, this would happen, but this totally might happen. Your supervisor probably knows more.) Thus, you'd need to re-write your code in C and/or in CUDA, with major and non-trivial investments towards memory alignment, pointer juggling, low-level optimisations, bandwidth optimisation, and what not. Writing fast low-level code takes a lot of time. It might be that this time is better spent doing other things.

This is a part of a publication build-up for a thesis, right? The way your supervisor envisions your thesis, this linear programming thing has no place there. (This is quite strange, as typically, as long as it is related (and it is) and successful, it does not really matter.)

Your supervisor has little expertise in that other field, does not feel like he/she can provide sufficient guidance, and would rather give up on that direction completely. This is also quite untypical, even if own expertise is lacking, one would typically be acquainted with colleagues, who are experts in that particular area. If a PhD candidate slowly wanders to that area, one might even think of a joint supervision.

So, to re-iterate. I do not know the rationale of your supervisor behind his/her decision, but it might be one of these. Do you have a good and informal enough relationship to simply ask why?

This method should work well for other data as it wraps around traditional linear programming methods and vectorizes them. The main thing is utilizing existing vectorization tools(MATLAB's strength) to solve many problems at once. You are right, I simply do not have time to code this up properly in C and/or CUDA. My publication record should not be a problem as is and my advisor would rather us publish fewer higher impact papers as opposed to many low-impact papers. As for the general direction, my advisor has little knowledge on the field and most has been independent. — 9 hours ago
I'll ask him when I see him again and inquire with some of the university's applied math department as I need some guidance there anyway with my Levenburg-Marquardt implementation. I'm Electrical Engineering so this is definitely not my or my advisor's field. — 9 hours ago
Communication is best solution, I guess. As for Levenberg-Marquardt, there is a levmar lib out there: github.com/bkloppenborg/simtoi/tree/master/lib/levmar-2.6 — 9 hours ago

geometrikal 44928 · Answer 3 · 2018-08-05 22:47:41Z

Loops can be slower in MATLAB, so using matrix operations to apply a particular algorithm to all the values is going to be faster than looping through the values and applying the algorithm individually. Since the number of calculations doesn't change, you haven't come up with anything scientifically novel, you have just found a way to use MATLAB more efficiently.

When I profiled your demo code in MATLAB, I noticed that the built-in fminbnd spent a lot of its time fetching a termination string and loading the optimisation settings structure. Maybe if this function was streamlined to the bare bones it would be much faster. The point is, these things are all just implementation details of same algorithm. Unless you are coming up with some previously unknown way of leveraging the CPU or GPU instruction set to speed up things I don't think the implementation is scientifically interesting.

So, your advisor is correct. You should focus on your primary research. The vectorisation has technical merit, speeding up things is a huge help (I spent hours and hours in front of MATLAB doing similar things, speed up roots for me please hehe). So I think you should properly document your code (no "I don't know what is going on here" easter eggs) and share it on File Exchange so that other people can take advantage of the tricks you have learnt. (GitHub as well, which has greater exposure)

Hard pill to swallow but you're probably correct. Tbh, it does irritate me how scientifically novel things are praised but technically novel things are not. For most of my research, the technical elements are what makes everything viable but all anyone cares about is the raw science. — 4 hours ago

Allure 13k104284 · Answer 4 · 2018-08-05 23:42:38Z

Figure out why your advisor recommends against publication.

If we assume that your advisor is a reasonable person, then he's probably against you publishing these results for concrete reasons. Why? Does he think it's not significant enough, not extendable, pointless, etc? If you can provide great counterarguments for your advisor's objections, then you have a good chance of changing your advisor's mind.

In some sense, your advisor is your first peer reviewer. If you can't change your advisor's mind, then you're not likely to convince an editor or reviewer either.

Geoffrey Brent 4,8361522 · Answer 5 · 2018-08-06 02:00:35Z

I will expand on a point that Oleg Lobachev mentioned in his answer:

Your new method seems to work very well on your data. Does it work well enough on other kinds of data? It might be the nature of your data that allows for such speedups. While this would still be of interest for your actual narrow topic, it might not qualify as a broad solution.

In areas where performance is important (including but not limited to mathematical algorithms), you will often find that standard benchmarks have been developed in order to compare different methods. These may include a range of difficult cases in order to get an idea not just of the method's speed, but also of its robustness.

If you have a new method that you think might be better than existing methods, I'd recommend looking for a relevant set of benchmark problems and testing it on those to get a picture of overall performance. You may find that it performs well on some problem classes but fails on others.

If you're lucky enough to find that your method reliably outperforms the market leaders, then that's a major advance and you should look to publish, or alternatively explore the possibility of commercialising it, depending on how you feel about such things and any restrictions that might apply.

In this case, something like Hans Mittelmann's "Benchmarks for Optimization Software" might be relevant. As an example, this page compares solver performance on a set of 46 linear problems. Gurobi, CPLEX, and Xpress were able to solve all 46 of the benchmark problems, with Gurobi being the fastest of those three by a small margin. MATLAB-R2018a solved 42/46 and was about ten times slower than Gurobi overall, according to the metric used.

Buffy 8,90433448 · Accepted Answer · 2018-08-05 17:22:54Z

It is good to have publications. It is also good to follow the advice of your advisor for many reasons. Advisors have some say over your future, of course, so caution is indicated, at least, in every case.

Note first that it has been many years since I was current with the algorithms of integer and linear programming. I suspect you are more current and your advisor more so, so be a bit careful in analyzing what I say below.

The field in general is quite mature and the existing algorithms are very sophisticated. This was true 30 year ago, in fact. If the field has settled down since then there is little urgency in publishing now, as it is unlikely that you would be beaten to publication if you wait. You can make your advisor happy and, indeed, make progress on your main work without abandoning what you have.

However, I think that a real advance should be questioned and you should be the one to question it. In particular, it may be that the reason for such good results is that your specific problem has characteristics that make this possible and your algorithm is nicely tailored to a special case. The possibility of that actually opens a door for your future work. If it is true, then knowing and describing that special case would be very useful, along with the algorithm.

Also, if it is, indeed, a special case and you have tested only with the confines of this case then your results may not apply generally. It would be good to know, before you publish, whether this is true or not. And it would be especially good for you if you are the one to discover this. Fortunately, you can test your algorithm on a wider class of problems found in the literature. Thus, you can, perhaps, rule out the situation in which you have an anomaly. But your primary work should likely come first.

Thank you, the main reason I'm unsure is that I'm not talking about the algorithm itself but rather the idea that linear programming can be vectorized for cases in which the function evaluation can be vectorized. Currently, there are ~10 functions I'm working with and this ideology applies to all of them largely because I am using traditional methods developed 50 years ago but in a way that makes them incredibly fast on modern computers. You are right though, I should respect my advisor for a variety of reasons while also testing the viability and usefulness of my method. — 10 hours ago
@Durkee, there have been a lot of books since, but 25 years ago, I found this book to be indispensable on the algorithms. amazon.com/Linear-Programming-Books-Mathematical-Sciences/dp/â€¦ — 9 hours ago
I prefer GÃ¤rtner and MatouÃ…Â¡ek for theory and geometric intuition and Vanderbei for the (baseline) practical details. — 9 hours ago

Oleg Lobachev 2,9311017 · Answer 7 · 2018-08-05 17:53:53Z

I do not know, who is "right". Your contributions look quite impressive, though. So I am trying here to come up with arguments that might lead your supervisor to his/her decision. I deliberately omit politics and strategising.

Your new method seems to work very well on your data. Does it work well enough on other kinds of data? It might be the nature of your data that allows for such speedups. While this would still be of interest for your actual narrow topic, it might not qualify as a broad solution.

You use MatLab. This is probably the correct tool for you to use. This might be not the right tool for the general claim. (In other words, you'd be more or less desk-rejected if you present your MatLab solution to the specialists in linear programming. I am not sure, this would happen, but this totally might happen. Your supervisor probably knows more.) Thus, you'd need to re-write your code in C and/or in CUDA, with major and non-trivial investments towards memory alignment, pointer juggling, low-level optimisations, bandwidth optimisation, and what not. Writing fast low-level code takes a lot of time. It might be that this time is better spent doing other things.

This is a part of a publication build-up for a thesis, right? The way your supervisor envisions your thesis, this linear programming thing has no place there. (This is quite strange, as typically, as long as it is related (and it is) and successful, it does not really matter.)

Your supervisor has little expertise in that other field, does not feel like he/she can provide sufficient guidance, and would rather give up on that direction completely. This is also quite untypical, even if own expertise is lacking, one would typically be acquainted with colleagues, who are experts in that particular area. If a PhD candidate slowly wanders to that area, one might even think of a joint supervision.

So, to re-iterate. I do not know the rationale of your supervisor behind his/her decision, but it might be one of these. Do you have a good and informal enough relationship to simply ask why?

This method should work well for other data as it wraps around traditional linear programming methods and vectorizes them. The main thing is utilizing existing vectorization tools(MATLAB's strength) to solve many problems at once. You are right, I simply do not have time to code this up properly in C and/or CUDA. My publication record should not be a problem as is and my advisor would rather us publish fewer higher impact papers as opposed to many low-impact papers. As for the general direction, my advisor has little knowledge on the field and most has been independent. — 9 hours ago
I'll ask him when I see him again and inquire with some of the university's applied math department as I need some guidance there anyway with my Levenburg-Marquardt implementation. I'm Electrical Engineering so this is definitely not my or my advisor's field. — 9 hours ago
Communication is best solution, I guess. As for Levenberg-Marquardt, there is a levmar lib out there: github.com/bkloppenborg/simtoi/tree/master/lib/levmar-2.6 — 9 hours ago

geometrikal 44928 · Answer 8 · 2018-08-05 22:47:41Z

Loops can be slower in MATLAB, so using matrix operations to apply a particular algorithm to all the values is going to be faster than looping through the values and applying the algorithm individually. Since the number of calculations doesn't change, you haven't come up with anything scientifically novel, you have just found a way to use MATLAB more efficiently.

When I profiled your demo code in MATLAB, I noticed that the built-in fminbnd spent a lot of its time fetching a termination string and loading the optimisation settings structure. Maybe if this function was streamlined to the bare bones it would be much faster. The point is, these things are all just implementation details of same algorithm. Unless you are coming up with some previously unknown way of leveraging the CPU or GPU instruction set to speed up things I don't think the implementation is scientifically interesting.

So, your advisor is correct. You should focus on your primary research. The vectorisation has technical merit, speeding up things is a huge help (I spent hours and hours in front of MATLAB doing similar things, speed up roots for me please hehe). So I think you should properly document your code (no "I don't know what is going on here" easter eggs) and share it on File Exchange so that other people can take advantage of the tricks you have learnt. (GitHub as well, which has greater exposure)

Hard pill to swallow but you're probably correct. Tbh, it does irritate me how scientifically novel things are praised but technically novel things are not. For most of my research, the technical elements are what makes everything viable but all anyone cares about is the raw science. — 4 hours ago

Allure 13k104284 · Answer 9 · 2018-08-05 23:42:38Z

Figure out why your advisor recommends against publication.

If we assume that your advisor is a reasonable person, then he's probably against you publishing these results for concrete reasons. Why? Does he think it's not significant enough, not extendable, pointless, etc? If you can provide great counterarguments for your advisor's objections, then you have a good chance of changing your advisor's mind.

In some sense, your advisor is your first peer reviewer. If you can't change your advisor's mind, then you're not likely to convince an editor or reviewer either.

Geoffrey Brent 4,8361522 · Answer 10 · 2018-08-06 02:00:35Z

I will expand on a point that Oleg Lobachev mentioned in his answer:

Your new method seems to work very well on your data. Does it work well enough on other kinds of data? It might be the nature of your data that allows for such speedups. While this would still be of interest for your actual narrow topic, it might not qualify as a broad solution.

In areas where performance is important (including but not limited to mathematical algorithms), you will often find that standard benchmarks have been developed in order to compare different methods. These may include a range of difficult cases in order to get an idea not just of the method's speed, but also of its robustness.

If you have a new method that you think might be better than existing methods, I'd recommend looking for a relevant set of benchmark problems and testing it on those to get a picture of overall performance. You may find that it performs well on some problem classes but fails on others.

If you're lucky enough to find that your method reliably outperforms the market leaders, then that's a major advance and you should look to publish, or alternatively explore the possibility of commercialising it, depending on how you feel about such things and any restrictions that might apply.

In this case, something like Hans Mittelmann's "Benchmarks for Optimization Software" might be relevant. As an example, this page compares solver performance on a set of 46 linear problems. Gurobi, CPLEX, and Xpress were able to solve all 46 of the benchmark problems, with Gurobi being the fastest of those three by a small margin. MATLAB-R2018a solved 42/46 and was about ten times slower than Gurobi overall, according to the metric used.

Search This Blog

ukmuiik

Should I publish a linear programming method despite my advisor's advice?

5 Answers
5

Your Answer

Post as a guest

5 Answers
5

5 Answers
5

Post as a guest

Comments

Post a Comment

Popular posts from this blog

Color the edges and diagonals of a regular polygon

Relationship between determinant of matrix and determinant of adjoint?

What is the equation of a 3D cone with generalised tilt?

Category

Random preview

Should I publish a linear programming method despite my advisor's advice?

5 Answers 5

Your Answer

Sign up or log in

Post as a guest

Post as a guest

5 Answers 5

5 Answers 5

Sign up or log in

Post as a guest

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Comments

Post a Comment

Popular posts from this blog

Color the edges and diagonals of a regular polygon

Relationship between determinant of matrix and determinant of adjoint?

What is the equation of a 3D cone with generalised tilt?

5 Answers
5

5 Answers
5

5 Answers
5